Discussion of Problem 1992. CVSAll operations except clone work O(1) in my program, but clone works in O(n). Despite that fact, my solution works in 0.218s New tests were added. Thank you. Edited by author 27.09.2020 14:29 Tests not check memory leaks, but check amount of used memory... Its weard. If you dont copy robot's stacks and just relink pointers, tests not check that you have lost memory Case Learn 1 1 Learn 1 2 .... Learn 1 n Clone 1 Rollback 1 Rollback 2 .... Rollback 1 Rollback 2 Learn 1 1 ... Learn 1 n In my solution in the end youll have n losted elements and n new elements in 1 robot that is assimptotically equal to copy all stacks Input: 14 4 learn 1 1 clone 1 learn 2 2 rollback 2 rollback 2 rollback 1 clone 2 learn 1 3 learn 2 4 relearn 3 relearn 3 check 1 check 2 check 3 Output: 3 4 2 I just have implemented "Copy on Write" strategy suggested in other tread and it helped me pass through tests #9 and #10 where I got MLE/TLE earlier. But I cannot pass #19. I tried StreamTokenizer suggested by "Getting Stated" page, then I even implemented my own parser without any cheking for input errors just to speed up my solution. But still too slow! There seems nothing can be done about algo itself: rollback/relearn fiddle with one variable, check prints, clone makes new entry in ArrayList<Clone> without actually doing anything. Only learn seems to be doing something: copying ProgramsList if it's needed, clearing abolished programs and adding new one. Not that much to find something excessive to remove. But why it take so much time in test #19? How did 26 genii get their AC with Java? Is there some kind of trick or fundamental improvement to achive better time? I lost my mind searching solution. Please, help! p.s. And sorry for bad English... Update: I removed clearing ArrayList<Integer> in learn command, it waste memory a little and save time a little and made some cosmetic improvements. But still too slow! Edited by author 21.12.2017 04:38 Edited by author 25.10.2017 18:58 #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 Я использовал для решения стратегию copy on write. I have used copy on write strategy. Когда я использовал scanf и printf, я получал TLE#9. When used scanf and prin tf got TLE#9. Когда заменил ввод на ввод через unlocked getchar и putchar, то получил АС за менее чем 0.6 сек. AC < 0.6 sec with _getchar_nolock and _putchar_nolock. Ну и немного на русском про саму COW-стратегию. Есть вектор реальных объектов клонов, а есть вектор ссылок на эти объекты. Новый объект в первом векторе создаётся не при клонировании, а при попытке изменить реального клона, на который есть больше одной ссылки. Во втором же векторе новые объекты создаются, напротив, только при клонировании. Можете объяснить, зачем даётся переменная m. Я успешно решил задачу без её использования: public static void Main() { var queryCount = int.Parse(Console.ReadLine().Split(' ')[0]); var queries = Enumerable .Range(0, queryCount) .Select(number => Console.ReadLine()) .ToArray(); foreach (var line in Solve(queries)) Console.WriteLine(line); } Не все люди решают задачи как Вы. Некоторым людям нужно количество запросов, чтобы, например, понять какого размера брать массив или тому подобное. Часто можно не учитывать какие то параметры, но это не значит, что они не нужны. All solutions have been rejudged with the current time limit. Also, few more tests have been added. 10 authors have got AC while 23 other have lost. I have replaced standart C# input functions with my low level parse method and got Accepted. Is this the goal of that rejudgement? Well, I just resubmitted the previous solution with visual c++. I do every query O(1) operations and use scanf and printf. I think the version of your g++ compiler is not that good. There were some troubles with scanf and printf at some new versions of g++ compiler. Used built-in Stack class, memory and time constraints seem to be OK. What could be the source of the problem? the limits of the variable Ci. From the statement: "It is also guaranteed that only the clones that already exist can occur in the queries." Worse case all command is clone. Max command (n) is 5x10^5 in instruction, so max clones are 5x10^5 = 500000 O(n) solution got TLE on test 9 ! Try this: Input: 19 5 learn 1 1 learn 1 2 learn 1 3 learn 1 4 rollback 1 rollback 1 relearn 1 clone 1 check 2 relearn 2 check 2 rollback 2 rollback 2 check 2 rollback 2 check 2 check 1 relearn 1 check 1 Expected output: 3 4 2 1 3 4 I am writing my solution in Java and I constantly getting "Memory Limit Exceeded" error on 10th test. I used ArrayList<Integer> to store 'programs' and 'rollbacks'. Then lately I changed it TIntArrayList, to store 'int' as a basic type, but still it does not solve the problem. I saw solutions in Java, that people used less than 10Mb of memory. What am I doing wrong? Edited by author 23.03.2014 18:03 Edited by author 23.03.2014 18:04 Fully rewrote the algorithm, to calculate the solution each time in runtime, without using memory for each clone, but then my solutions exceeds Time limitation on 9th test. I also do not understand why we get a number 'm' - number of educational program. How this number could help us to solve the problem? Finally solved it. The main trick was to find a way to make clone operation without coping all the clone memory. I got AC with #define I(x) int x; cin >> x #define F(i,n) for(int i = 0; i < (n); ++i) int main(){ cin.sync_with_stdio(false); I(n); I(m); F(i,n){ string w; cin >> w; I(j); auto& c = clones[j-1]; if(w == "learn"){ // ... Looks like this is related only to C#. Does Pj becomes last program learned for clone Ci even if Pj was first learned program for clone Ci ? 1. *deleted* 2. It's possible for the input file size to exceed 6 MB. In C++, reading it from cin is out of the question, and scanf() is apparently slow too. getchar() is faster. Edited by author 27.10.2013 14:02 Your test is incorrect, "If a clone learn (not relearn) a program, all cancellation record history of this clone is deleted". So we can't do "relearn" in last line. First test is test from statment, and it is correct Your first solution has a bug, so it falls with runtime Oh, found it. Using a buffer of 8 chars to read the command's name was a terrible idea (one more is needed for '\0'), but it worked fine on my local machine. Is there a way to track such access violations locally? Deleted the first "hint" to avoid causing confusion. |
|