oj.uz

Submission #962720

# Submission time Handle Problem Language Result Execution time Memory
962720 2024-04-14T07:27:25 Z NValchanov Game (IOI13_game) C++17
10 / 100
 3181 ms 256000 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;
typedef long long ll;

const ll MAXN = 2010;
const ll MAXM = 2010;
const ll MAXLOG = 17;

long long gcd2(long long X, long long Y) {

    if(X == 0 && Y == 0)
        return 0;
    else if(X == 0 && Y != 0)
        return Y;
    else if(X != 0 && Y == 0)
        return X;

    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

ll n,m;
ll a[MAXN][MAXM];
ll sparse[MAXN][MAXM][MAXLOG];
ll lg[MAXM];

void init(int R, int C)
{
    n = R;
    m = C;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            for(int k = 0; k < MAXLOG; k++)
            {
                sparse[i][j][k] = 0;
            }
        }
    }
    for(int i = 2; i <= m; i++)
    {
        lg[i] = lg[i / 2] + 1;
        ///cout << "Logarithm base 2 from " << i << " is " << lg[i] << endl;
    }
}

void calc(int i)
{
    for(int k = 1; k < MAXLOG; k++)
    {
        for(int j = 0; j < m; j++)
        {
            ll first = sparse[i][j][k - 1];
            ll second = sparse[i][j + (1 << (k - 1))][k - 1];
            sparse[i][j][k] = gcd2(first, second);
        }
    }
}

void update(int i, int j, long long k)
{
    a[i][j] = k;
    sparse[i][j][0] = k;
    calc(i);
}

ll query_sparse(ll i, ll l, ll r)
{
    ll len = r - l + 1;
    ll k = lg[len];

    return gcd2(sparse[i][l][k], sparse[i][r - (1 << k) + 1][k]);
}

ll query(int i1, int j1, int i2, int j2)
{
    ///cout << "For query from " << "(" << i1 << ";" << j1 << ")" << " to " << "(" << i2 << ";" << j2 << ")" << endl;
    ll result = query_sparse(i1, j1, j2);
    ///cout << "GCD from " << i1 << " to " << i1 << " is " << result << endl;
    for(int i = i1 + 1; i <= i2; i++)
    {
        ll cur = query_sparse(i, j1, j2);
        result = gcd2(result, cur);
        ///cout << "GCD for row " << i << " is " << cur << endl;
        ///cout << "GCD from " << i1 << " to " << i << " is " << result << endl;
    }
    return result;
}

ll calculate(int i1, int j1, int i2, int j2)
{
    return query(i1, j1, i2, j2);
}
/**
int main()
{
    ll r,c,n;
    cin >> r >> c >> n;
    init(r,c);

    for(int i = 0; i < n; i++)
    {
        ll type;
        cin >> type;
        if(type == 1)
        {
            ll x,y,w;
            cin >> x >> y >> w;
            update(x,y,w);

            cout << endl << endl << "Sparse Table : " << endl;

            for(int j = 0; j < r; j++)
            {
                for(int k = 0; k < c; k++)
                {
                    cout << sparse[j][k][1] << " ";
                }
                cout << endl;
            }
            cout << endl << endl;
        }
        else
        {
            ll i1,j1,i2,j2;
            cin >> i1 >> j1 >> i2 >> j2;

            cout << calculate(i1, j1, i2, j2) << endl;
        }
    }

    return 0;
}
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 5 ms 31068 KB Output is correct
3 Correct 5 ms 31176 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 5 ms 31068 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 3 ms 22876 KB Output is correct
9 Correct 6 ms 31252 KB Output is correct
10 Correct 4 ms 31192 KB Output is correct
11 Correct 4 ms 31068 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Runtime error 3181 ms 38028 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 5 ms 31068 KB Output is correct
3 Correct 5 ms 31068 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 5 ms 31320 KB Output is correct
7 Correct 1 ms 4560 KB Output is correct
8 Correct 3 ms 22872 KB Output is correct
9 Correct 5 ms 31064 KB Output is correct
10 Correct 4 ms 31068 KB Output is correct
11 Correct 4 ms 31068 KB Output is correct
12 Runtime error 116 ms 256000 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 5 ms 31132 KB Output is correct
3 Correct 5 ms 31068 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 3 ms 27112 KB Output is correct
6 Correct 5 ms 31068 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 3 ms 22876 KB Output is correct
9 Correct 5 ms 31064 KB Output is correct
10 Correct 4 ms 31068 KB Output is correct
11 Correct 4 ms 31068 KB Output is correct
12 Runtime error 2842 ms 38036 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 5 ms 31068 KB Output is correct
3 Correct 5 ms 31064 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 5 ms 31068 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 3 ms 22872 KB Output is correct
9 Correct 4 ms 31064 KB Output is correct
10 Correct 4 ms 31068 KB Output is correct
11 Correct 4 ms 31068 KB Output is correct
12 Runtime error 2957 ms 38032 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -