oj.uz

Submission #93846

# Submission time Handle Problem Language Result Execution time Memory
93846 2019-01-12T12:14:17 Z alexpetrescu Game (IOI13_game) C++14
10 / 100
 324 ms 257024 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 209 ms 6748 KB Output is correct
3 Correct 225 ms 6776 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 10 ms 6776 KB Output is correct
6 Correct 207 ms 6648 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 5 ms 2296 KB Output is correct
9 Correct 204 ms 6648 KB Output is correct
10 Correct 62 ms 6620 KB Output is correct
11 Correct 78 ms 6688 KB Output is correct
12 Correct 1 ms 376 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Runtime error 324 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 227 ms 6720 KB Output is correct
3 Correct 223 ms 6688 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 10 ms 6648 KB Output is correct
6 Correct 221 ms 6684 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 4 ms 2296 KB Output is correct
9 Correct 211 ms 6724 KB Output is correct
10 Correct 63 ms 6648 KB Output is correct
11 Correct 82 ms 6648 KB Output is correct
12 Runtime error 287 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 222 ms 6724 KB Output is correct
3 Correct 208 ms 6748 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 9 ms 6648 KB Output is correct
6 Correct 223 ms 6776 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 4 ms 2168 KB Output is correct
9 Correct 202 ms 6780 KB Output is correct
10 Correct 57 ms 6648 KB Output is correct
11 Correct 79 ms 6648 KB Output is correct
12 Runtime error 281 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 212 ms 6684 KB Output is correct
3 Correct 219 ms 6780 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 10 ms 6648 KB Output is correct
6 Correct 209 ms 6620 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 4 ms 2300 KB Output is correct
9 Correct 204 ms 6748 KB Output is correct
10 Correct 58 ms 6648 KB Output is correct
11 Correct 77 ms 6776 KB Output is correct
12 Runtime error 234 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -