Common Board#include <iostream> #include <vector> using namespace std; string per(int x) { int k(0),b(x); string m; if (x<10) {m+=char(x+'0');return m;} while(x!=0) { x=x/10; k++; } x=b; b=k; string s; while(k>0) { s+=char((x%10)+'0'); x=(x-x%10)/10; k--; } for(int i=0;i<b;i++) m+=s[b-i-1]; return m; } int main() { int n,m,i,j,p,t(1); char s[80]; string Y; vector<int> v; vector<int> w; v.reserve(1); w.reserve(1); scanf("%d",&n); scanf("%d",&m); for(int d=0;d<n;d++) { scanf("%s",s); if(s[0]=='l') { scanf("%d%d",&i,&j); if(j>m) continue; if(t<i) continue; v.push_back(j);w.push_back(i); p=w.size(); for(int x=0;x<p;x++) if(w[x]==i && v[x]<0) {v.erase(v.begin()+x);w.erase(w.begin()+x);} } if(s[0]=='r'&& s[1]=='o') { scanf("%d",&i); p=w.size()-1; while(v[p]<0 || w[p]!=i) p--; v[p]-=1000000;} if(s[0]=='c'&& s[1]=='h') { scanf("%d",&i); if(w.size()>0) { for(int x=w.size()-1;x>=0;x--) if(w[x]==i && v[x]>0) {Y+=per(v[x]);if(d!=n-1)Y+="\n";break;} else if (x==0) {Y+="basic";if(d!=n-1)Y+="\n";} } else {Y+="basic";if(d!=n-1) Y+="\n";} } if(s[0]=='r'&& s[1]=='e') { scanf("%d",&i); p=0; while(v[p]>0 || w[p]!=i) { p++; if(p>w.size()-1) break; } if(p>=0) v[p]+=1000000; } if(s[0]=='c'&& s[1]=='l') { if(t<i) continue; t++; scanf("%d",&i); p=w.size(); for(int x=0;x<p;x++) if(w[x]==i) {v.push_back(v[x]);w.push_back(t);} } } cout<<Y; } I can't make up any new tests. Everything, I tried, works. If you have some ideas, please, help Edited by author 01.08.2017 15:26 Edited by author 01.08.2017 15:28 The problem is connected with recoil #include <iostream> #include <string> #include <map> #include <vector> #include <cctype> #include <algorithm> #include <math.h> #include <iostream> using namespace std; int main() { int N = 0, k = 0; string s; getline (cin, s); char name; for (auto i = 0; i < (int)s.length(); i++) { name = s[i]; if (name == 'a' || name == 'd' || name == 'g' || name == 'j' || name == 'm' || name == 'p' || name == 's' || name == 'v' || name == 'y' || name == '.' || name == ' ') { k = 1; N += k; } if (name == 'b' || name == 'e' || name == 'h' || name == 'k' || name == 'n' || name == 'k' || name == 't' || name == 'w' || name == 'z' || name == ',') { k = 2; N += k; } if (name == 'c' || name == 'f' || name == 'i' || name == 'l' || name == 'o' || name == 'r' || name == 'u' || name == 'x' || name == '!') { k = 3; N += k; } } cout << N; return 0; } You forgot 'q' in the second if 2 1 3 1 4 3 5 1 6 4 7 2 8 6 9 8 10 7 ans: 8 or 1 The problem is very simple. It is clear from the first glance what is going on. The coding is trivial. The math part is trivial. And... for some reason it is almost impossible to get AC from the first try. Можно просто перебирать ответ наименьшего возможного, двойки, пока не найдем нужное значение. Для данного количества жителей можно за log этого количества по времени найти требуемое количество кондукторов. Здесь пишут про int_64, про "не использовать double" и "использовать epsilon=1e-9". В моём варианте такое не нужно Хватило int_32 и double. Никакого epsilon, сравнения непосредственно оператором <=. #include <iostream> #include <string> #include <map> #include <vector> #include <cctype> #include <algorithm> #include <math.h> #include <iostream> using namespace std; int main() { int N, ch; int h = 1; int max = 0; int second_max = 0; cin >> N; vector <int> m(N); vector<int> v(N); vector<int> k; for (int i = 0; i < N; i++) { cin >> ch; v[i] = ch; } for(int i = 1; i < N; i++) { if(v[i] > max) { second_max = max; max = v[i]; } else { if (v[i] > second_max) { second_max = v[i]; } } } for (int i = 0; i < N; i++) { if (v[i] != max && v[i] != second_max && v[i] != v[0]) { k.push_back(v[i]); } } sort(begin(k), end(k)); m[0] = v[0]; m[1] = second_max; m[N - 1] = max; for (int i = 2; i < N-1; i++) { m[i] = k[k.size() - h]; h++; } for (auto j = 0; j < N; j++) { for (auto i = 0; i < N; i++) { if(m[j] == v[i]) { cout << i + 1 << " "; i = N; } } } return 0; } Please explain your solution Можно сдать тернарным поиском на Python 3.4 с параметрами : количество итераций -- 100 максимальное А и максимальное B -- 10**18 My AC program had TL when we have this test (with a log of garbage, but still acceptable by task conditions) 131 393 struct used .int .int struct aa .int .int struct ab .aa .aa struct ac .ab .ab // many lines...... struct ew .ev .ev struct ex .ew .ew struct ey .ex .ex struct ez .ey .ey 000000010000000200000003 Can you add this? Link to full test - https://gist.github.com/Izaron/1a4fd5894f45fafc2d6d46f0f8d81ce3I solved this problem( 0.015 sec) but My algo is heuristic. Why this problem is geometric? Or how can we use geometry in this task to reduce the search? I think there might be as well a mistake in tags. To me, this problem reminds of http://acm.timus.ru/problem.aspx?space=1&num=1326 with minor differences: 1) cities = bottle taps 2) N <= 30 instead of N <= 20; 3) city's "group" is a list of cities hit when bombing this one. Insert this magic line before the code #pragma comment(linker, "/STACK:36777216") And it works! That is not magic That line sets stack size to 16 MB And you forgot the most important thing The code works ONLY with Microsoft Visual C++ #include <iostream> #include <iomanip> using namespace std; int main() { setlocale(LC_ALL,"Russian"); int a,b; cin>>a>>b; a=a+b; cout<<"a+b="<<a<<endl; return 0; } Посмотри на прример. Что надо вывести? А теперь посмотри, что выводит твоя программа. Не находишь ничего лишнего? Как прикажешь компьютеру проверять твой ответ? да уж, думал тут действительно нормальные задачи, а задание через зад написано =( Обратите, пожалуйста, внимание К каждой задаче даётся хотя бы один пример ввода/вывода I had WA25 when used char[20002]; After changed to char[30002] got AC. 0 /Yes 1 1 0 10000 /Yes 1 5 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 /Yes 2 1 0 2 1 1 3 /No 2 1 1 3 1 0 2 /No 2 1 1 1000 1 1001 2000 /No 2 3 1 10 11 20 21 30 1 5 26 /Yes 2 3 1 10 11 20 21 30 1 5 25 /No 2 1 21 30 1 5 25 /No 4 2 4 5 6 7 1 4 7 1 3 6 1 2 5 /No Thank You very much. Now I got AC. I found mistake in my programm. It's a lot help checking the board here before submitting. I got AC with one shot. 2 1 0 2 1 1 3 /No 2 1 1 3 1 0 2 /No can you explain why? OK, i got it. [0,2] contains only {0, 1} cells, but i thought {0, 1, 2} I was so upset that I wa on #7 more than 10. I want to practice my suffix array,so I used it and used RMQ,But I wa on #7. I very want to know what is #7. Can the admin give the simple to me? thanks a lot http://paste.ubuntu.com/23169621/the suffix array algorithm is right cause I got AC ever using this Template~~ I got ac now cause I use a character '$' to end my suffix array . I think is ok but got wa on 7..why? Latin alphabet letters is not abcdefg.....ABCDGEF...? no no no . cause my book[] is smaller. book[500 + 20] is not enough? I see . the length of string is 2000 Edited by author 12.09.2016 21:19 Приятно было прикоснуться к наследию легендарного человека Я знаю, что здесь еще есть от него задача Currency Exchange For some reason I get TLE with G++ 4.9 and AC with Visual C++ 2013 with exactly the same code. I tried to use scanf/printf instead of cin/cout, but had no difference. On my machine this code works <100ms for every n with G++. Can anyone explain why I get TLE with G++? Thanks! #include <string> #include <queue> #include <iostream> using namespace std; int main() { int n; cin >> n; queue<string> result; result.push("a"); result.push("b"); result.push("c"); char abc[] = {'a', 'b', 'c'}; for (int i = 1; i < n; i++) { while (true) { string &s = result.front(); if (s.size() > i) { break; } char last = s[s.size() - 1]; if (s.size() > 1) { char lbo = s[s.size() - 2]; for (int k = 0; k < 3; k++) { char c = abc[k]; if (last != c && lbo != c) { result.push(s + c); } } } else { for (int k = 0; k < 3; k++) { char c = abc[k]; if (last != c) { result.push(s + c); } } } result.pop(); } if ((i + 1) * result.size() > 100000) { cout << "TOO LONG"; return 0; } } while (!result.empty()) { cout << result.front() << endl; result.pop(); } return 0; } Because s+c is a temporary object You are creating temporary objects and throwing them away O(N) times Looks like G++ failed to notice that it is unnecessary to create and destroy objects And MSVC noticed that and replaced with something more effective no bitwise shit needed, no storing 17 bits for indexes and no such stuff! just use unsigned stack* [1000] for the stacks (store elements in a dynamic array, reallocating memory for each push), and unsigned top[1000] for the index of the top element. with this i got AC with 663 KB! good luck! Looks like solve the problem in such a manner is no longer possible Because ,as of 2017, there is no Intel C++ compiler And every other compiler fails to allocate memory effective Probably when reallocating there are empty spaces which count as memory used And Intel Compiler was able to get rid of such spaces. После того как наконец сдал, хочется сказать, что на самом деле OP очень переусложнил задачу, динамическая память не нужна. Достаточно статического выделения. Которое к слову очень быстро работает -- за 31 мс. Я много раз ловил WA#8. Здесь предлагали тест на WA#8. Тест у меня работал хорошо. Ошибка, как выяснилось, была в том, что я перепутал переменную с названием block_size с переменной block_cnt. Edited by author 26.07.2017 16:19 Одно из решений использовало сдвиг O(N) ячеек массива каждую операцию Ценой диких оптимизаций удалось довести его до TLE#16 (только на Clang, любой другой компилятор C++ позволял получить только TLE#12) Edited by author 26.07.2017 16:21 As stated in the statement, after spraying or aromatizing of fruit it may become to have fractional value. 25th test is the first case where you need to aromatize one flower and dearomatize another in such way that both of them have fractional value, but their sum is integer. Edited by author 07.11.2009 05:19 I've changed my algorithm, but have got WA25->WA19. Who knows what does it mean? Nevermind, I had a stupid bug with bitmasks (I'm wondering how it could pass 19-25 tests). Thank you very much, this was a non-obvious test. Try this test: 100000 99999 0 1 2 1000000 2 3 1000000 ... 99999 100000 1000000 Answer: 10049708502000000 Good Luck! Thanks! HINT for solvers: In the test above, you can get an overflow. Change min(⌈(1 + T/100)* ti⌉, 100500*ti) to long long my_ceil(long long tnow, long long f1, long long t) { if(h1+tnow-f1>h2*h1) return h2*t; //return min(ceil(t+(tnow-f1)*t/100.0), h2*t); if(((tnow-f1)*t) % h1==0) return t+((tnow-f1)*t)/h1; else return t+((tnow-f1)*t)/h1 + h3; } //h1=100; h2=100500; h3=1; where tnow=time now, f1=last cleaning time for this rib, s2=start time of next cleaning Edited by author 26.07.2017 14:10 Solution looks like bruteforce with a precalc, not a dynamic programming one. Or precalc counts as DP? Or DP is just a clever bruteforce? Edited by author 25.07.2017 20:10 Are you calculating something like "maximal sum subarray" ? That is where it is DP. If you are doing Kadane algorithm You are doing essentially that thing dp[i] = max(0, dp[i-1] + matrix [i]) answer = max(dp[i]) |
|