oj.uz

Submission #384030

# Submission time Handle Problem Language Result Execution time Memory
384030 2021-03-31T08:23:25 Z Keshi Game (IOI13_game) C++17
36 / 100
 4509 ms 214344 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;
	if(r > maxn || c > maxn) cout << 1/0;
}

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 < 0 || y < 0 || 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 dp[0][P][Q];
}

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

Compilation message

game.cpp: In function 'void init(int, int)':
game.cpp:43:36: warning: division by zero [-Wdiv-by-zero]
   43 |  if(r > maxn || c > maxn) cout << 1/0;
      |                                   ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 12 ms 2668 KB Output is correct
3 Correct 12 ms 2668 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 13 ms 2668 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 9 ms 2668 KB Output is correct
10 Correct 5 ms 2156 KB Output is correct
11 Correct 3 ms 1260 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Runtime error 12 ms 492 KB Execution killed with signal 4
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 12 ms 2668 KB Output is correct
3 Correct 12 ms 2668 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 12 ms 2668 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 9 ms 2668 KB Output is correct
10 Correct 5 ms 2176 KB Output is correct
11 Correct 3 ms 1260 KB Output is correct
12 Correct 1809 ms 82388 KB Output is correct
13 Correct 1683 ms 73068 KB Output is correct
14 Correct 1020 ms 6684 KB Output is correct
15 Correct 3070 ms 129700 KB Output is correct
16 Correct 4335 ms 212832 KB Output is correct
17 Correct 1958 ms 196436 KB Output is correct
18 Correct 3984 ms 214216 KB Output is correct
19 Correct 3964 ms 214344 KB Output is correct
20 Correct 4509 ms 213296 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 13 ms 2668 KB Output is correct
3 Correct 12 ms 2668 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 12 ms 2668 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 9 ms 2668 KB Output is correct
10 Correct 5 ms 2156 KB Output is correct
11 Correct 2 ms 1260 KB Output is correct
12 Runtime error 12 ms 492 KB Execution killed with signal 4
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 12 ms 2668 KB Output is correct
3 Correct 12 ms 2668 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 13 ms 2668 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 9 ms 2668 KB Output is correct
10 Correct 5 ms 2156 KB Output is correct
11 Correct 2 ms 1260 KB Output is correct
12 Runtime error 12 ms 492 KB Execution killed with signal 4
13 Halted 0 ms 0 KB -