oj.uz

Submission #962722

# Submission time Handle Problem Language Result Execution time Memory
962722 2024-04-14T07:28:40 Z NValchanov Game (IOI13_game) C++17
10 / 100
 5597 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 = 10;

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 2392 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 3 ms 18912 KB Output is correct
7 Correct 2 ms 4440 KB Output is correct
8 Correct 6 ms 14680 KB Output is correct
9 Correct 4 ms 18780 KB Output is correct
10 Correct 3 ms 18780 KB Output is correct
11 Correct 3 ms 18780 KB Output is correct
12 Correct 1 ms 2396 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 2396 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Runtime error 1438 ms 25856 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 3 ms 18780 KB Output is correct
3 Correct 3 ms 18912 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 3 ms 18912 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 14680 KB Output is correct
9 Correct 3 ms 18780 KB Output is correct
10 Correct 2 ms 18780 KB Output is correct
11 Correct 4 ms 18788 KB Output is correct
12 Correct 4654 ms 182564 KB Output is correct
13 Correct 5597 ms 179800 KB Output is correct
14 Runtime error 85 ms 256000 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 3 ms 18776 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 4 ms 18780 KB Output is correct
10 Correct 2 ms 18912 KB Output is correct
11 Correct 2 ms 18780 KB Output is correct
12 Runtime error 1401 ms 25808 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 2392 KB Output is correct
2 Correct 3 ms 18776 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 16852 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 18780 KB Output is correct
10 Correct 2 ms 18780 KB Output is correct
11 Correct 3 ms 18780 KB Output is correct
12 Runtime error 1469 ms 25812 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -