Submission #962720

#	Time	Username	Problem	Language	Result	Execution time	Memory
962720		NValchanov	Game (IOI13_game)	C++17	10 / 100	3181 ms	256000 KiB

game

#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 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20