oj.uz

Submission #578998

# Submission time Handle Problem Language Result Execution time Memory
578998 2022-06-18T09:36:07 Z Belgutei Game (IOI13_game) C++17
37 / 100
 938 ms 27112 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

vector<ll> v[10][30];
int level,zereg[30];

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 val;
int l,r;

void dfs(int num, int k, int x) {
    int y = zereg[level - k] * x;
    int z = zereg[level - k] * (x + 1) - 1;
    if(l <= y && z <= r) {
        val = gcd2(val, v[num][k][x]);
        return;
    }
    if(z < l || y > r || k == level) return;
    dfs(num, k + 1, x * 2);
    dfs(num, k + 1, x * 2 + 1);
}

int rr,cc;
ll z[200][200];
bool ok = 0;

void init(int R, int C) {
    /* ... */
    if(R <= 100 && C <= 100) {
        ok = 1;
        return;
    }
    zereg[0] = 1;
    for(int i = 0; i <= 30; i ++) {
        if(zereg[i] >= C) {
            level = i;
            break;
        }
        zereg[i + 1] = zereg[i] * 2;
    }
    for(int x = 0; x < R; x ++) {
        for(int i = 0; i <= level; i ++) {
            for(int j = 0; j < zereg[i]; j ++) {
                v[x][i].pb(0);
            }
        }
    }
}

void update(int P, int Q, long long K) {
    if(ok == 1) {
        z[P][Q] = K;
        return;
    }
    v[P][level][Q] = K;
    for(int i = level - 1; i >= 0; i --) {
        Q /= 2;
        v[P][i][Q] = gcd2(v[P][i + 1][Q * 2], v[P][i + 1][Q * 2 + 1]);
    }
    // for(int i = 0; i <= level; i ++) {
    //     for(int j = 0; j < zereg[i]; j ++) {
    //         cout << v[P][i][j] << ' ' ;
    //     }
    //     cout << '\n';
    // }
    /* ... */ 
}

long long calculate(int P, int Q, int U, int V) {
    long long ret = 0;
    if(ok == 1) {
        for(int i = P; i <= U; i ++) {
            for(int j = Q; j <= V; j ++) {
                ret = gcd2(ret, z[i][j]);
            }
        }
        return ret;
    }
    //cout << "FK: " << P << ' ' << Q << ' ' << U << ' ' << V << '\n';
    for(int i = P; i <= U; i ++) {
        val = 0;
        l = Q;
        r = V;
        dfs(i,0,0);
        ret = gcd2(val,ret);
    //    cout << ret << " // \n";
    }
    return ret;
    /* ... */
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 280 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 336 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 938 ms 26100 KB Output is correct
5 Correct 550 ms 26304 KB Output is correct
6 Correct 645 ms 23068 KB Output is correct
7 Correct 626 ms 22928 KB Output is correct
8 Correct 570 ms 23704 KB Output is correct
9 Correct 639 ms 23020 KB Output is correct
10 Correct 609 ms 22504 KB Output is correct
11 Correct 0 ms 212 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Runtime error 2 ms 724 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 873 ms 26812 KB Output is correct
13 Correct 560 ms 27032 KB Output is correct
14 Correct 660 ms 23688 KB Output is correct
15 Correct 630 ms 23580 KB Output is correct
16 Correct 585 ms 24336 KB Output is correct
17 Correct 639 ms 23564 KB Output is correct
18 Correct 609 ms 23296 KB Output is correct
19 Runtime error 1 ms 724 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 890 ms 26596 KB Output is correct
13 Correct 552 ms 27112 KB Output is correct
14 Correct 649 ms 23712 KB Output is correct
15 Correct 662 ms 23708 KB Output is correct
16 Correct 563 ms 24256 KB Output is correct
17 Correct 625 ms 23576 KB Output is correct
18 Correct 611 ms 23212 KB Output is correct
19 Runtime error 1 ms 724 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -