oj.uz

답안 #384016

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
384016 2021-03-31T08:08:49 Z Keshi 게임 (IOI13_game) C++17
10 / 100
 13000 ms 135404 KB 
//In the name of God
#include <bits/stdc++.h>
#include "game.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 2013;
const ll maxm = 2013;
const ll lg = 7;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define lc (id << 1)
#define rc (lc | 1)


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

int r, c;
ll dp[lg][maxn][maxn];

void init(int R, int C) {
    r = R;
	c = C;
}

void update(int P, int Q, long long K) {
	dp[0][P][Q] = K;
    for(int i = 1; i < lg; i++){
		for(int x = P; P - x < (1 << i); x--){
			for(int y = Q; Q - y < (1 << i); y--){
				if(x + (1 << i) > r || y + (1 << i) > c) continue;
				dp[i][x][y] = gcd2(gcd2(dp[i - 1][x][y], dp[i - 1][x + (1 << (i - 1))][y]),
						gcd2(dp[i - 1][x][y + (1 << (i - 1))], dp[i - 1][x + (1 << (i - 1))][y + (1 << (i - 1))]));
			}
		}
	}
}

long long calculate(int P, int Q, int U, int V) {
	ll g = 0;
	for(ll i = lg; i--;){
		if((1 << i) > U - P + 1 || (1 << i) > V - Q + 1) continue;
		for(int x = P; x <= U; x += (1 << i)){
			if(x + (1 << i) > U) x = U + 1 - (1 << i);
			for(int y = Q; y <= V; y += (1 << i)){
				if(y + (1 << i) > V) y = V + 1 - (1 << i);
				g = gcd2(g, dp[i][x][y]);
			}
		}
		return g;
	}
	return g;
}

/*int main(){
    freopen("sample.in", "r", stdin);

	int R, C, M;
	
	cin >> R >> C >> M;
	init(R, C);
	for(int i = 0; i < M; i++){
		ll x, a, b, cc, d;
		cin >> x >> a >> b >> cc;
		if(x == 1){
			update(a, b, cc);
		}
		else{
			cin >> d;
			cout << calculate(a, b, cc, d) << "\n";
		}
	}

    return 0;
}*/

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 20 ms 3308 KB Output is correct
3 Correct 19 ms 3308 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 20 ms 3308 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 1004 KB Output is correct
9 Correct 17 ms 3308 KB Output is correct
10 Correct 9 ms 2668 KB Output is correct
11 Correct 9 ms 1772 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Execution timed out 13014 ms 7300 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 20 ms 3308 KB Output is correct
3 Correct 19 ms 3308 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 20 ms 3308 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 1004 KB Output is correct
9 Correct 18 ms 3308 KB Output is correct
10 Correct 9 ms 2668 KB Output is correct
11 Correct 9 ms 1772 KB Output is correct
12 Correct 1798 ms 84460 KB Output is correct
13 Correct 2185 ms 76908 KB Output is correct
14 Correct 981 ms 11188 KB Output is correct
15 Incorrect 3493 ms 135404 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 21 ms 3436 KB Output is correct
3 Correct 19 ms 3308 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 20 ms 3308 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 1004 KB Output is correct
9 Correct 17 ms 3308 KB Output is correct
10 Correct 9 ms 2668 KB Output is correct
11 Correct 9 ms 1792 KB Output is correct
12 Execution timed out 13016 ms 7280 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 20 ms 3308 KB Output is correct
3 Correct 19 ms 3308 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 20 ms 3308 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 1004 KB Output is correct
9 Correct 18 ms 3308 KB Output is correct
10 Correct 9 ms 2668 KB Output is correct
11 Correct 9 ms 1772 KB Output is correct
12 Execution timed out 13003 ms 7164 KB Time limit exceeded
13 Halted 0 ms 0 KB -