Submission #384028

#	Time	Username	Problem	Language	Result	Execution time	Memory
384028		Keshi	Game (IOI13_game)	C++17	0 / 100	79 ms	5484 KiB

game

//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) exit(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))]));
				cout << i << " " << x << " " << y << " -> " << dp[i][x][y] << "\n";
			}
		}
	}
}

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

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20