oj.uz

Submission #945944

# Submission time Handle Problem Language Result Execution time Memory
945944 2024-03-14T08:58:56 Z vjudge1 Game (IOI13_game) C++17
10 / 100
 13000 ms 198652 KB 
#include "game.h"
#include<bits/stdc++.h>
 
using namespace std;
 
#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()                 
#define sz(a) (int)a.size()
#define s second
#define f first
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
const int N = 2e3 + 5;
 
int n, m, lg[N];
ll vl[N][N], up[N][N][6];
 
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 get(int R, int l, int r) {
	int k = lg[r - l + 1], p = l;
	if (1 << (2 * k) > r - l + 1 || (1 << (2 * k + 2) <= r - l + 1)) exit(0);
	ll res = 0;
	while (true) {
		res = gcd2(res, up[R][p][k]);
		p += (1 << (2 * k));
		if (p > r) break;
		p = min(p, r - (1 << (2 * k)) + 1);
	}
	return res;
}
 
void bld(int R) {
	for (int k = 0; k < 6; k++) {
		for (int i = 0; i < m - (1 << (2 * k)) + 1; i++) {
			if (k) {
				int v = (1 << (2 * k - 2));
				up[R][i][k] = gcd2(up[R][i][k - 1], up[R][i + v][k - 1]);
				up[R][i][k] = gcd2(up[R][i][k], up[R][i + 2 * v][k - 1]);
				up[R][i][k] = gcd2(up[R][i][k], up[R][i + 3 * v][k - 1]);
			}else up[R][i][k] = vl[R][i]; 
		} 
	}
}
 
void init(int R, int C) {
    n = R, m = C;
    lg[0] = -1;
    for (int i = 1; i <= m; i++) {
    	lg[i] = lg[i / 4] + 1;
	}
	cout << '\n';
}
 
void update(int P, int Q, ll K) {//
	vl[P][Q] = K;
	bld(P);    
}
 
ll calculate(int P, int Q, int U, int V) {
	ll ans = 0;
	for (int i = P; i <= U; i++) {
		ans = gcd2(ans, get(i, Q, V));
	}
	return ans;
}

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 14680 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 14680 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 2 ms 10584 KB Output is correct
12 Correct 1 ms 2392 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 2396 KB Output is correct
4 Runtime error 5 ms 344 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 2396 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 14680 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 14680 KB Output is correct
10 Correct 1 ms 10588 KB Output is correct
11 Correct 2 ms 10740 KB Output is correct
12 Correct 12348 ms 75004 KB Output is correct
13 Correct 11585 ms 71476 KB Output is correct
14 Correct 2355 ms 34128 KB Output is correct
15 Execution timed out 13058 ms 198652 KB Time limit exceeded
16 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 2 ms 14684 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct
12 Runtime error 6 ms 348 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 2396 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 1 ms 10588 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct
12 Runtime error 5 ms 376 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -