oj.uz

Submission #78559

# Submission time Handle Problem Language Result Execution time Memory
78559 2018-10-06T09:53:36 Z Charis02 Crayfish scrivener (IOI12_scrivener) C++14
34 / 100
 1000 ms 123248 KB 
#include<stdio.h>
#include<algorithm>
#define ll int
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 1000004

using namespace std;

ll root;
ll countt = 0;
ll dp[N][21];
ll ldp[N][21];
ll length[N];
bool isupdate[N];
char ans[N];

ll newNode()
{
    isupdate[countt] = false;
    length[countt] = 0;

    countt++;

    return countt-1;
}

void Init()
{
    root = newNode();
}

bool ison(ll x,ll i)
{
    return (bool)(x&(1 << i));
}

ll jump(ll cur,ll x)
{
    if(dp[cur][x])
        return dp[cur][x];

    return dp[cur][x] = jump(jump(cur,x-1),x-1);
}

ll ancestor(ll cur,ll x)
{
    if(x == 0)
        return cur;

    ll res = cur;

    rep(i,0,20)
    {
        if(ison(x,i))
        {
            res = jump(res,i);
        }
    }

    return res;
}


ll letterjump(ll cur,ll x)
{
    if(ldp[cur][x])
        return ldp[cur][x];

    return ldp[cur][x] = letterjump(letterjump(cur,x-1),x-1);
}

ll letterancestor(ll cur,ll x)
{
    if(x == 0)
        return cur;

    ll res = cur;

    rep(i,0,20)
    {
        if(ison(x,i))
        {
            res = letterjump(res,i);
        }
    }

    return res;
}

void TypeLetter(char c)
{
    ll p = root;
    root = newNode();
    dp[root][0] = p;

    if(isupdate[p])
    {
        ldp[root][0] = ldp[p][0];
    }
    else
    {
        ldp[root][0] = p;
    }

    length[root] = length[p] + 1;
    ans[root] = c;

    return;
}

void UndoCommands(ll x)
{
    ll p = root;
    ll rp = ancestor(p,x);

    root = newNode();
    dp[root][0] = p;

    if(isupdate[rp])
    {
        ldp[root][0] = ldp[rp][0];
    }
    else
    {
        ldp[root][0] = rp;
    }

    isupdate[root] = true;
    length[root] = length[rp];
    ans[root] = '0';

    return;
}

char GetLetter(int P)
{
    return ans[letterancestor(root,(length[root]) - P - (ll)(!isupdate[root]))];
}

/*
int main()
{
    n = read();

    rep(i,0,n)
    {
        type = gc();

        while(type < 'A' || type > 'Z')
            type = gc();

        if(type == 'T')
        {
            c = gc();

            while(c < 'a' || c > 'z')
                c = gc();

            typechar(c,root);
        }
        else if(type == 'U')
        {
            d = read();
            undo(d,root);
        }
        else
        {
            d = read();

            printf("%c\n",(letterancestor(root,(root -> length) - d - (ll)(!(root -> isupdate))) -> ans));
        }
    }

    return 0;
}*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 516 KB Output is correct
6 Correct 2 ms 564 KB Output is correct
7 Correct 2 ms 584 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 2 ms 668 KB Output is correct
10 Correct 2 ms 672 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 676 KB Output is correct
2 Correct 2 ms 676 KB Output is correct
3 Correct 2 ms 676 KB Output is correct
4 Correct 2 ms 676 KB Output is correct
5 Correct 2 ms 676 KB Output is correct
6 Correct 2 ms 680 KB Output is correct
7 Correct 2 ms 680 KB Output is correct
8 Correct 2 ms 680 KB Output is correct
9 Correct 2 ms 680 KB Output is correct
10 Correct 2 ms 776 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 932 KB Output is correct
2 Correct 4 ms 1060 KB Output is correct
3 Correct 4 ms 1316 KB Output is correct
4 Correct 4 ms 1316 KB Output is correct
5 Correct 4 ms 1316 KB Output is correct
6 Correct 4 ms 1444 KB Output is correct
7 Correct 4 ms 1444 KB Output is correct
8 Correct 4 ms 1444 KB Output is correct
9 Correct 4 ms 1444 KB Output is correct
10 Correct 6 ms 1448 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1026 ms 123248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1029 ms 123248 KB Time limit exceeded
2 Halted 0 ms 0 KB -