Submission #578998

#	Time	Username	Problem	Language	Result	Execution time	Memory
578998		Belgutei	Game (IOI13_game)	C++17	37 / 100	938 ms	27112 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

vector<ll> v[10][30];
int level,zereg[30];

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
ll val;
int l,r;

void dfs(int num, int k, int x) {
    int y = zereg[level - k] * x;
    int z = zereg[level - k] * (x + 1) - 1;
    if(l <= y && z <= r) {
        val = gcd2(val, v[num][k][x]);
        return;
    }
    if(z < l || y > r || k == level) return;
    dfs(num, k + 1, x * 2);
    dfs(num, k + 1, x * 2 + 1);
}

int rr,cc;
ll z[200][200];
bool ok = 0;

void init(int R, int C) {
    /* ... */
    if(R <= 100 && C <= 100) {
        ok = 1;
        return;
    }
    zereg[0] = 1;
    for(int i = 0; i <= 30; i ++) {
        if(zereg[i] >= C) {
            level = i;
            break;
        }
        zereg[i + 1] = zereg[i] * 2;
    }
    for(int x = 0; x < R; x ++) {
        for(int i = 0; i <= level; i ++) {
            for(int j = 0; j < zereg[i]; j ++) {
                v[x][i].pb(0);
            }
        }
    }
}

void update(int P, int Q, long long K) {
    if(ok == 1) {
        z[P][Q] = K;
        return;
    }
    v[P][level][Q] = K;
    for(int i = level - 1; i >= 0; i --) {
        Q /= 2;
        v[P][i][Q] = gcd2(v[P][i + 1][Q * 2], v[P][i + 1][Q * 2 + 1]);
    }
    // for(int i = 0; i <= level; i ++) {
    //     for(int j = 0; j < zereg[i]; j ++) {
    //         cout << v[P][i][j] << ' ' ;
    //     }
    //     cout << '\n';
    // }
    /* ... */ 
}

long long calculate(int P, int Q, int U, int V) {
    long long ret = 0;
    if(ok == 1) {
        for(int i = P; i <= U; i ++) {
            for(int j = Q; j <= V; j ++) {
                ret = gcd2(ret, z[i][j]);
            }
        }
        return ret;
    }
    //cout << "FK: " << P << ' ' << Q << ' ' << U << ' ' << V << '\n';
    for(int i = P; i <= U; i ++) {
        val = 0;
        l = Q;
        r = V;
        dfs(i,0,0);
        ret = gcd2(val,ret);
    //    cout << ret << " // \n";
    }
    return ret;
    /* ... */
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20