Submission #93846

#	Time	Username	Problem	Language	Result	Execution time	Memory
93846		alexpetrescu	Game (IOI13_game)	C++14	10 / 100	324 ms	257024 KiB

game

#include "game.h"
#include <cstring>
#include <vector>
#include <algorithm>

std::vector < std::vector < std::vector < std::vector < long long > > > > rmq;
int nrlin, nrcol, lg2[100001];

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;
}

void init(int R, int C) {
    nrlin = R;
    nrcol = C;
    int n = std::max(nrlin, nrcol);
    for (int i = 2; i <= n; i++)
        if ((1 << (lg2[i - 1] + 1)) == i)
            lg2[i] = lg2[i - 1] + 1;
        else
            lg2[i] = lg2[i - 1];
    rmq.resize(nrlin);
    for (int i = 0; i < nrlin; i++) {
        rmq[i].resize(nrcol);
        for (int j = 0; j < nrcol; j++) {
            rmq[i][j].resize(lg2[nrlin] + 1);
            for (int a = 0; a < lg2[nrlin] + 1; a++) {
                rmq[i][j][a].resize(lg2[nrcol] + 1);
                for (int b = 0; b < lg2[nrcol] + 1; b++)
                    rmq[i][j][a][b] = 0;
            }
        }
    }
}

void update(int P, int Q, long long K) {
    rmq[P][Q][0][0] = K;
    for (int i = P; i < nrlin; i++) {
        for (int j = Q; j < nrcol; j++) {
            for (int b = 1; (1 << b) <= j + 1; b++)
                rmq[i][j][0][b] = gcd2(rmq[i][j][0][b - 1], rmq[i][j - (1 << (b - 1))][0][b - 1]);
            for (int a = 1; (1 << a) <= i + 1; a++)
                for (int b = 0; (1 << b) <= j + 1; b++)
                    rmq[i][j][a][b] = gcd2(rmq[i][j][a - 1][b], rmq[i - (1 << (a - 1))][j][a - 1][b]);
        }
    }
}

long long calculate(int P, int Q, int U, int V) {
    int a = lg2[U - P + 1], b = lg2[V - Q + 1];
    return gcd2(gcd2(gcd2(rmq[U][V][a][b], rmq[P + (1 << a) - 1][V][a][b]), rmq[U][Q + (1 << b) - 1][a][b]), rmq[P + (1 << a) - 1][Q + (1 << b) - 1][a][b]);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

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