oj.uz

답안 #945951

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
945951 2024-03-14T09:01:54 Z mansur 게임 (IOI13_game) C++17
10 / 100
 13000 ms 219056 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], pw[7];
ll vl[N][N], up[N][N][7];
 
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;
	ll res = 0;
	while (true) {
		res = gcd2(res, up[R][p][k]);
		p += pw[k];
		if (p > r) break;
		p = min(p, r - pw[k] + 1);
	}
	return res;
}
 
void bld(int R) {
	for (int k = 0; k < 7; k++) {
		for (int i = 0; i < m - pw[k] + 1; i++) {
			if (k) {
				int v = pw[k - 1];
				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]);
			}else up[R][i][k] = vl[R][i]; 
		} 
	}
}
 
void init(int R, int C) {
    n = R, m = C;
    lg[0] = -1;
    pw[0] = 1;
    for (int i = 1; i < 7; i++) pw[i] = pw[i - 1] * 3;
    for (int i = 1; i <= m; i++) {
    	lg[i] = lg[i / 3] + 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 3 ms 16732 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 468 KB Output is correct
6 Correct 2 ms 16728 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 10840 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 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 508 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 16732 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 16732 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 10844 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 5238 ms 81480 KB Output is correct
13 Correct 7094 ms 77052 KB Output is correct
14 Correct 2223 ms 32540 KB Output is correct
15 Execution timed out 13106 ms 219056 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 3 ms 16728 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 16732 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 10844 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Runtime error 5 ms 348 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 1 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 16732 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 14800 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Runtime error 5 ms 348 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -