oj.uz

Submission #1090440

# Submission time Handle Problem Language Result Execution time Memory
1090440 2024-09-18T11:11:36 Z vjudge1 Game (IOI13_game) C++14
10 / 100
 13000 ms 16328 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd2(ll X, ll Y)
{
    if (!X)
        return Y;
    ll an = __builtin_ctzll(X | Y);
    X >>= __builtin_ctzll(X);
    Y >>= __builtin_ctzll(Y);
    while (Y)
    {
        if (X > Y)
            swap(X, Y);
        Y -= X;
        Y >>= __builtin_ctzll(Y);
    }
    return X << an;
}
ll T = 1;
vector<ll> sg = {0};
vector<int> pa = {0}, cl = {-1}, cr = {-1}, wl = {0}, wr = {0}, wt = {0}, wb = {0};
void cre(int i, int x)
{
    sg.push_back(0);
    pa.push_back(i);
    cl.push_back(-1);
    cr.push_back(-1);
    if (wr[i] - wl[i] > wb[i] - wt[i])
    {
        ll md = ((wl[i] + wr[i]) >> 1);
        wt.push_back(wt[i]);
        wb.push_back(wb[i]);
        if (x)
        {
            wl.push_back(md);
            wr.push_back(wr[i]);
        }
        else
        {
            wl.push_back(wl[i]);
            wr.push_back(md);
        }
    }
    else
    {
        ll md = ((wt[i] + wb[i]) >> 1);
        wl.push_back(wl[i]);
        wr.push_back(wr[i]);
        if (x)
        {
            wt.push_back(md);
            wb.push_back(wb[i]);
        }
        else
        {
            wt.push_back(wt[i]);
            wb.push_back(md);
        }
    }
    if (x)
        cr[i] = T;
    else
        cl[i] = T;
    T++;
}
int l, r, t, b;
ll x;
void upd(int i)
{
    if (wt[i] > l || wb[i] <= l || wl[i] > r || wr[i] <= r)
        return;
    if (wt[i] == l && wb[i] == l + 1 && wl[i] == r && wr[i] == r + 1)
    {
        sg[i] = x;
        return;
    }
    if (cl[i] == -1)
        cre(i, 0);
    upd(cl[i]);
    if (cr[i] == -1)
        cre(i, 1);
    upd(cr[i]);
    sg[i] = gcd2(sg[cl[i]], sg[cr[i]]);
}
ll qu(int i)
{
    if (wt[i] >= b || wb[i] <= t || wl[i] >= r || wr[i] <= l)
        return 0;
    if (wt[i] >= t && wb[i] <= b && wl[i] >= l && wr[i] <= r)
        return sg[i];
    ll an = 0;
    if (cl[i] != -1)
        an = gcd2(qu(cl[i]), an);
    if (cr[i] != -1)
        an = gcd2(qu(cr[i]), an);
    return an;
}
void init(int R, int C)
{
    wr[0] = C;
    wb[0] = R;
}
void update(int P, int Q, ll K)
{
    l = P;
    r = Q;
    x = K;
    upd(0);
}
ll calculate(int P, int Q, int U, int V)
{
    t = P;
    b = U + 1;
    l = Q;
    r = V + 1;
    return qu(0);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 432 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 432 KB Output is correct
12 Correct 0 ms 436 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 13062 ms 5496 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 432 KB Output is correct
12 Correct 5532 ms 16328 KB Output is correct
13 Execution timed out 13032 ms 6352 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Execution timed out 13054 ms 5536 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Execution timed out 13090 ms 5756 KB Time limit exceeded
13 Halted 0 ms 0 KB -