All operations except clone work O(1) in my program, but clone works in O(n). Despite that fact, my solution works in 0.218s

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

Я использовал для решения стратегию 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.

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.

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

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"){
    // ...

I have TLE with time 0.6s but in problem statement 1s

http://acm.timus.ru/status.aspx?space=1&num=1992&author=31927

Looks like something wrong with checker of problem statement.

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