Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
HINT | Wonsei | 1654. Шифровка | 6 фев 2021 20:27 | 3 |
HINT Wonsei 15 сен 2020 19:52 Use stacks. Push one letter by letter. If stack.top() == current letter, pop the stack. else push the letter in the stack. Re: HINT Lifeisbeautiful 6 янв 2021 10:19 Re: HINT Eusebiu_distrugatorul 6 фев 2021 20:27 |
Code not producing any output? | Naman Sharma | 1654. Шифровка | 20 май 2020 13:21 | 2 |
#include<bits/stdc++.h> using namespace std; stack<char> S; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); string s; cin >> s; int len = s.length(); for(int i = 0; i < len;i++) { char c; if(S.empty()) c = 0; else c = S.top(); if(c == s[i]) S.pop(); else S.push(c); } string ans = ""; len = S.size(); for(int i = 0; i < len;i++) { char c = S.top(); ans += c; S.pop(); } reverse(ans.begin(),ans.end()); cout << ans; } You should do S.push(s[i]) in your else clause inside the for loop. |
Stuck on Test 6? Read Here! | Davanish | 1654. Шифровка | 8 апр 2020 23:22 | 6 |
For Time limit exceeded: If you get time limit exceeded, it must mean that you're trying to modify the input string (i.e. trying to delete i-th chars). Try creating a new OUTPUT string without modifying the INPUT string. Note: if you're using a high language such as java or C#, try using the StringBuilder object to build your output string. For Wrong Answer(WA): If you get WA, try some of these test cases: Input: "dddd" Output: "" Input: "ddddd" Output: "d" Input: "abba" Output: "" Input: "abbbbac" Output: "c" Input: "wliisddsmmleeddw" Output: "" Input: "avcbbffcv" Output: "a" Hope this helps. Edited by author 12.07.2012 00:47 Input: "abbbbac" Output: "c" Спасибо, помогло! For Time limit exceeded: If you get time limit exceeded, it must mean that you're trying to modify the input string (i.e. trying to delete i-th chars). Try creating a new OUTPUT string without modifying the INPUT string. Note: if you're using a high language such as java or C#, try using the StringBuilder object to build your output string. For Wrong Answer(WA): If you get WA, try some of these test cases: Input: "dddd" Output: "" Input: "ddddd" Output: "d" Input: "abba" Output: "" Input: "abbbbac" Output: "c" Input: "wliisddsmmleeddw" Output: "" Input: "avcbbffcv" Output: "a" Hope this helps. Edited by author 12.07.2012 00:47 Thanks a lot...I could'n understand the problem statement first, now, reading ur comment I clearly understood the problem. for me problem was that program was returning "axx" on "aaaxx" Edited by author 18.03.2017 19:56 |
ac 0.015 | Dyryaev Daniil | 1654. Шифровка | 30 окт 2019 15:05 | 1 |
ac 0.015 Dyryaev Daniil 30 окт 2019 15:05 #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cmath> #include <algorithm> #include <set> #include <vector> #include <string> #include <cstdlib> using namespace std; void optimization() { cin.tie(nullptr); ios_base::sync_with_stdio(false); } int main() { optimization(); string s; int k = -1; cin >> s; char c[200000]; for (char & i : c) { i = ' '; } for (char i : s) { if (k > -1) { if (c[k] == i) { c[k] = ' '; k--; } else { k++; c[k] = i; continue; } } else { k++; c[k] = i; } } for (char i : c) { if (i != ' ') { cout << i; } } return 0; } |
AC C++ | soroush | 1654. Шифровка | 12 авг 2019 12:27 | 1 |
AC C++ soroush 12 авг 2019 12:27 #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MAX = 1e5+10; const ll ZERO = 0; #define endl '\n' #define dokme(x) cout << x ; return(0); #define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); stack < char > stk; int main(){ migmig; stk.push('.'); char c[200001]; cin >> c; int n=strlen(c); for (int i =0; i < n ; i ++ ){ if (stk.top()!=c[i]){ stk.push(c[i]); } else{ stk.pop(); } } n=stk.size()-1; memset(c,0,sizeof(c)); for (int i = 0 ; i<n ; i ++ ){ c[n-i-1]=stk.top(); stk.pop(); } cout << c; } |
Tle in 6? Look at source code. | Cebiyev_Ferhad_Qafqaz U. | 1654. Шифровка | 12 июл 2019 20:08 | 4 |
#include <iostream> #include <cstdlib> #include <deque> using namespace std; int main() { int h; char s[200001]; scanf("%s", &s); int n=strlen(s); deque<char> v (s, s + n );
if(v.size()==2 && v[0]==v[1] ) return 0; b: h=2; for(int i=0; i<v.size()-1 ;i++) if(v[i] == v[i+1]) { v.erase(v.begin() + i); v.erase(v.begin() + i); h=1; } if(h==1) goto b;
for(int i=0; i<v.size(); i++) cout << v[i];
return 0; } Hello, If you are still working on this, let you know that it can't be solved with erase. I implemented a similar algorithm in Java which goes through the string and deletes the successful characters and it also got TLE on test 6.The easiest way is removing the successful characters as you read them. nc->new character from the input. if(i!=-1&&c[i]==nc){//new char is equal to the char at the end of the string, remove it i--; }else{ //add the new char to the string i++; c[i]=nc; } Hope this helps You got TLE because deque has poor deletion performance on positions other than the front and back. |
0.109s answer | dula | 1654. Шифровка | 12 июн 2019 11:39 | 6 |
#include<iostream> #include<string.h> #include<deque> #include<stdio.h> using namespace std; int main() { string node; cin >> node; int one,two; one = 0; two = 1; int pre = 0; for(int i = 0;i < node.size();i++) { if(node[i] == '!') continue; if(node[i] == node[i+1]) { node[i] = node[i+1] = '!'; one = pre; if(i+2 < node.size()) two = i+2; while(one> 0 && two < node.size()) { while(one > 0 && node[one] == '!') one--; if(node[one] == node[two] ) { node[one] = node[two] = '!'; one--;two++; } else break; } } else pre = i; }
for(int i = 0;i < node.size();i++) { if(node[i] != '!') cout << node[i]; }
} I use stack and my solution works 0.064s :) My solution works 0.048s ;) Why your solutions is right? if input is: sddssdds then your ans is "ss"! |
If you have WA #3 | german_goncharov | 1654. Шифровка | 2 апр 2019 03:53 | 1 |
For test you can use this string: hkjgnnngkikipipekkfkfgg Correct result is: hkjgngkikipipefkf |
how to make faster? | TSU_TheScull | 1654. Шифровка | 2 апр 2019 03:05 | 1 |
using System; namespace pain { class Program { static void Main(string[] args) { string s = Console.ReadLine(); char[] ss = new char[s.Length]; for (int i = 0; i < s.Length; i++) ss[i] = s[i]; for (int i = 0; i < s.Length - 1;) { if (ss[i] == ss[i + 1]) { if (i - 1 >= 0) { int n = i + 2; b: if (n <= s.Length - 1) { if (ss[n] != ' ') { ss[i] = ss[n]; ss[n] = ' '; ss[i + 1] = ' '; } else { n++; goto b; } } else break; } else { ss[i] = ' '; ss[i + 1] = ' '; } if (i >= 1) i--; else i++; } else i++; } for (int i = 0; i < s.Length; i++) if(ss[i] != ' ') Console.Write(ss[i]); //Console.Write(st2(s)); Console.ReadLine(); } public static string st1(string s, ref int n) { if (s.Length - 1 > n) { if (s[n] == s[n + 1]) { s = s.Remove(n, 2); if (n >= 2) n -= 2; else n--; } n++; s = st1(s, ref n); } return s; } public static string st2(string s) { for (int i = 0; i < s.Length - 1; i++) { if (s[i] == s[i + 1]) { s = s.Remove(i, 2); if (i >= 2) i -= 2; } } return s; } public static string st3(string s) { int n = 0; int nt = s.Length - 1; string[] ss = new string[nt]; for (int i = 0; i < nt; i++) { bool d = false; for (int j = i; j < nt; j++) { if (ss[i] == s[j].ToString()) { d = true; } } if (!d) { ss[n] = s[i].ToString(); n++; } } n = 0; while (nt != 0) { nt = s.Length; for (int i = 0; i < ss.Length; i++) { s = s.Replace(ss[i] + ss[i], ""); } if (nt == s.Length) break; } return s; } } } Edited by author 02.04.2019 03:06 |
WA2 | DenisBordachkov | 1654. Шифровка | 15 фев 2019 02:29 | 1 |
WA2 DenisBordachkov 15 фев 2019 02:29 Why Wring answer? import java.util.Scanner; public class T1654 { public static char[] arr; public static String out = ""; public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); String inp = sc.next(); sc.close(); arr = new char[inp.length()]; arr = inp.toCharArray(); format(); if(out != "") { System.out.println(out); } else { System.out.println(""); }
}
public static void format() { boolean isFormat = false; int l = arr.length; for(int i = 0; i< l-1; i++) { if(arr[i] == arr[i+1]) { arr[i] = 0; arr[i+1] = 0; isFormat = true; } else if(arr[i] != arr[i+1] & arr[i] != 0){ out += arr[i]; } } out+= arr[arr.length-1]; if(isFormat == true) { arr = new char[out.length()]; arr = out.toCharArray(); out = ""; format(); } } } |
A simple python script to generate long test cases | Xitsa | 1654. Шифровка | 27 ноя 2018 09:08 | 1 |
import random letters = ['a' ,'b' ,'c' ,'d' ,'e' ,'f' ,'g' ,'h' ,'i' ,'j' ,'k' ,'l' ,'m' ,'n' ,'o' ,'p' ,'q' ,'r' ,'s' ,'t' ,'u' ,'v' ,'w' ,'x' ,'y' ,'z'] example = 'xitsa' while len(example) < 199999: letter = random.choice(letters) point = random.randrange(0, len(example)) example = example[:point] + letter + letter + example[point:] print(example) |
why stack so long | IlushaMax | 1654. Шифровка | 1 окт 2018 13:38 | 2 |
I thought that stack is the best thing in this case but I've seen 0.015 and 0.001 sec . I've got 0.046 Maybe it's because of the choice of language. I use C++17 and it run in 0.001s |
little asvice (no spoilers) | bstu_student | 1654. Шифровка | 9 авг 2018 09:09 | 1 |
char[200001] gives perfect time if you will check repeats while string is inputting |
use printf() instead of cout and string instead of char if you use c++ stl | Haloom | 1654. Шифровка | 9 авг 2018 09:08 | 2 |
i used deque. cout got me TLE.using printf save me. if(st.front()!=s[i]) { st.emplace_front(s[i]); } else st.pop_front();
for(it=st.end()-1; it>=st.begin(); it--) { printf("%c",*it); } i say more - it's better don't use stl-containers if it's possible. char[200001] gives perfect time |
Time limit exceeded on tes 8 (java), i dont know which way is excellent | Aydar | 1654. Шифровка | 21 мар 2018 06:11 | 4 |
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Iterator; import java.util.Stack; public class problem1654 { public static void main(String[] args) throws IOException { BufferedReader inp = new BufferedReader(new InputStreamReader(System.in)); String str=inp.readLine(); Stack<Character> st=new Stack<Character>(); st.push(str.charAt(0)); String s=""; for(int i=1;i<str.length();i++){ if(!st.empty()&&st.peek()==str.charAt(i)) st.pop(); else{ st.push(str.charAt(i));
} }
while(!st.empty()){ s=s+st.pop(); } int n=s.length(); for(int i=0;i<n;i++){ System.out.print(s.charAt(n-i-1));
} }} When i used stack(from STL) in C++, i'd got TL8. But after i realzed stack by using array, i got AC your reply help me very much!3Q Don't use : while(!st.empty()){ s=s+st.pop(); } -------- Use this phrase at the end of your Code: Iterator<Character> b = st.iterator(); while(b.hasNext()){ System.out.print(b.next()); } |
wh Test 3 | Mr.Creative | 1654. Шифровка | 10 янв 2018 15:20 | 1 |
// Harry Poter #include <stdio.h> #include <iostream> #include <stdlib.h> #include <string.h> using namespace std; int main() { char line[200001], w2[200001]; cin.getline(line, sizeof(line)); int t = 0, i; for(i = 0; i < strlen(line); i++){ if (line[i] == line[i + 1]) { i++; A: if (line[i + 1] != line[i + 2]) { if (t != 0 && w2[t - 1] == line[i + 1]) {t--; i += 1; goto A;} } } else {w2[t++] = line[i];} } w2[t] = '\0'; printf("%s", w2); } |
For those who have WA#4 | Sandu Petrasco | 1654. Шифровка | 29 авг 2016 12:07 | 2 |
The test is "abcdeedcbaabcdeedcba"(without quotes). The answer should be ""(empty string). hey mi anwser code is the same, what is the bug |
wa #4 | gerson | 1654. Шифровка | 29 авг 2016 12:00 | 1 |
wa #4 gerson 29 авг 2016 12:00 hey if one else to know print the anser plese say me..in the test #4 i have a empty string, but the judge say me "wa" in test #4.... why??? help me please. #include <bits/stdc++.h> using namespace std; int main(){ string cad,res; cin>>cad; res = ""; int tam = cad.length(); int i,j; i=0; j=1; int boolean[tam]={0}; while(j<tam){ if(cad[i]==cad[j]){ boolean[i] = 1; boolean[j] = 1; if(i-1>=0){ i-=1; j+=1; }else{ i=j+1; j+=2; } }else{ i=j; j+=1; } } for(int i=0;i<tam;i++){ if(boolean[i]==0) res+=cad[i]; } cout<<res; return 0; } |
WA#5 | Dewesh Deo Singh | 1654. Шифровка | 25 дек 2015 13:34 | 3 |
WA#5 Dewesh Deo Singh 19 дек 2015 12:45 Can any body tell me whai is in the test case 5...??? My code seems right but everytime it says WA#5... 200000 char in test case #5!! Re: WA#5 Dewesh Deo Singh 25 дек 2015 13:34 Thanksss.. It helped me a lot... Edited by author 25.12.2015 13:35 |
I'm trying to use stack. It's true ! Why ? | TruongNT | 1654. Шифровка | 22 дек 2015 07:45 | 1 |
import java.util.Scanner; import java.util.Stack; public class CliperMessage_1654_Stack { public static void main(String[] arg1) { Scanner sc=new Scanner(System.in); StringBuilder sb=new StringBuilder(); Stack<Character> stc=new Stack<>(); sb.append(sc.nextLine()); if(sb.length()<=200000){ for(int i=0;i<sb.length();i++){ if(stc.isEmpty()||(stc.peek()!=sb.charAt(i))) stc.push(sb.charAt(i)); else if((stc.peek()==sb.charAt(i))) stc.pop();
}
StringBuilder sbn=new StringBuilder(); int j=0; while(!stc.empty()) sbn.insert(j++, ""+stc.pop()); System.out.println(sbn.reverse()); } } } |