Any hint for solving this problem?

:)

In C#, I was getting TLE using LinkedList, so I rewrote everything using an array of 2*10^6 elements. It passed in 1.7s (thank god), but that's still very slow. How do people get times like 0.2s?

tle 42 -ios_base::sync_with_stdio(0);
but ios_base::sync_with_stdio(false); cin.tie(NULL); - ACCEPTED with 0.015)

Clang++ 4.0.1 - 0.39s - Accepted
G++ 7.1 - 0.421 - Accepted
Visual C++ 2017 - 1.029 - Time limit exceeded

rofl

in general i noticed that for the most problems clang is usually faster then g++ or ms c++


Edited by author 21.08.2018 03:53

Java coders:
Use BufferedReader and PrintWriter for IO!

http://acm.timus.ru/status.aspx?space=1&num=1915&author=106686&count=100

;)

Edited by author 23.12.2015 02:45

Edited by author 23.12.2015 02:46

This task almost pisses me off. I was finally accepteed after writing my own input/output via fgetc/fputc. Both stream and printf/scanf lead to TLE on test 42. To be onest i still beleive that stream is faster than printf/scanf... But i really wonder which IO uses those guys/girls who accepted with less than 0.2 or something...

Edited by author 27.08.2016 13:09

Edited by author 27.08.2016 13:09

Is there a way to know more precisely what is going on on the test machine?
I've tested my python solution on my machine on large data (N=10^6) with a lot of copying operations (geometric progression) and got answer with memory used < 64Mb.

I used Java: The following I did.
1. Declare Stack<Integer>.
like this:         Stack<Integer> st = new Stack<Integer>();
                   boolean ok = false; <--// this boolean is tricky.. :))
2. Then, I iterate from 1 to n init i read X and i checked three given if statements in input. They are:
1.if(x>0){st.push(x);}
2.if(x==-1){pw.println(st.pop());}
3.if(x==0){
       int len = st.size();
       if(2*len<=n){
                st.addAll((Collection) st.clone());
    } else{
           if(!ok){
// here If you don't use this if statement you will have Memory Limit #42...
                      st.addAll((Collection<? extends Integer>) st.clone());
             ok=true;
            }
    }
}
Problem is copying all stack elements...
What I am really doing here is using stack clone() method. But When you do so many clones will have MemLimit. That's why I checked that my Stack size and its copies are more than N (2*len>n) then I should copy the whole stack one time not more.
And I am thinking that above code worked because <b<stack size wansn't big enough when I cloned last time....

Sorry If I am mistaken and poor english. But this code AC ...

what is test 5?

How to prevent TLE? I use LinkedList (can AddFirst and AddLast) and use max size of set = n.

this is simple test for TEST 25.
10
-1
0
1
2
0
0
-1
-1
-1
2

Answer :
2
1
2

Edited by author 07.11.2013 16:13

This my results. For this task, time limit is 1.0 second, so why it happend with 0.265 time?

5520909    12:24:55 21 фев 2014    svg2003    1915. Руины титанов: воссоздание былого    Visual C# 2010    Time limit exceeded    42    0.265    49 708 КБ

Edited by author 21.02.2014 12:30

Edited by author 21.02.2014 12:31

No need for scanf/printf, just do cin.sync_with_stdio(false) and get 0.5 seconds with 13 lines of code (hint: use deque).

When I use G++11 I always get TLE,but once I try vc++2010 to submit my code , I got AC.
I wasted too much time.Any can expalin it for me ?
This is my code:#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
const int MAXN = 1000000 + 10;
int a[2 * MAXN];
using namespace std;
int main()
{
    int n;
    scanf("%d", &n);
    int i = 1;
    while (n--)
    {
        int t;
        scanf("%d", &t);
        if (t > 0)
            a[i++] = t;
        else if (t == -1)
            printf("%d\n", a[--i]);
        else if (t == 0)
        {
            if (i - 1 <= n)
            {
                int num = min(i - 1, n);
                for (int j = 1; j <= num; ++j)
                {
                    a[i] = a[i-num];
                    ++i;
                }
            }
        }
    }
    //system("pause");
    return 0;
}

Edited by author 26.04.2013 15:20

The problem say that "It is guaranteed that during the experiment each time a coin was to be removed the stack was not empty."
But when I submit such a brute force code:
--------------------
        if (x > 0) a[t++] = x;
        else if (x == 0) {
            if (t + t < maxn) {
                copy(a, a + t, a + t);
                t += t;
            }
        }
        else printf("%d\n", a[--t]);
--------------------
It crashed at #42. Then, I modified the last "else branch" into:
--------------------
        else if (t) printf("%d\n", a[--t]);
--------------------
I got WA at #42.

request for any optimizations possible for python solution: not it get TLE #42

import sys

#sys.stdin = open("smalltest.txt")
#sys.stdin = open("input.txt")

top = 0
stack = [0] * 2000020
input = sys.stdin.read().split()
operations = int(input[0])
ans = ""

for i in xrange(operations) :
    op = int(input[i+1])
    if op > 0 :
        stack[top] = op
        top += 1
    elif op < 0 :
        top -= 1
        ans += str(stack[top]) + "\n"
    else :
        if operations - i > top :
            l = max( 0, top - operations + i )
            cnt = top - l
            stack[top:top+cnt] = stack[l:top]
            top += cnt

sys.stdout.write( ans )

where the number 8 in the output test?
4
3
8
4
3
8
out: 4 3 8 4
out: 4 3 4 3 is correct?

What is test 6?

Edited by author 11.01.2013 21:21