oj.uz

Submission #29937

# Submission time Handle Problem Language Result Execution time Memory
29937 2017-07-21T11:02:30 Z ozaslan Game (IOI13_game) C++14
37 / 100
 13000 ms 41084 KB 
#include <bits/stdc++.h>
#include <stdio.h>
#include "game.h"
#define max_N 100001

long long gcd2(long long X, long long Y) {
	//printf("X\n");
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

long long mat[1000][1000];
long long st[10][max_N * 4];
int sa, su, sub;

void init(int R, int C) {
	sa = R;
	su = C;
	if(R > 10) sub = 1;
	else sub = 3;
}

void guncelle(int dugum, int sol, int sag, int satir, int sutun, long long K) {

    if (sol == sag) {
        st[satir][dugum] = K;
        return;
    }

    int orta = (sol + sag) / 2;

    if (orta >= sutun)
        guncelle(dugum*2, sol, orta, satir, sutun, K);
    else
        guncelle(dugum*2+1, orta+1, sag, satir, sutun, K);

    st[satir][dugum] = gcd2(st[satir][dugum*2], st[satir][dugum*2+1]);
}

void update(int P, int Q, long long K) {
    if (sub == 3)guncelle(1, 0, su-1, P, Q, K);
    else mat[P][Q] = K;
}

long long sorgu(int dugum, int sol, int sag, int satir, int aSol, int aSag) {
   // printf("Dugum: %d, sol: %d, sag: %d, satir: %d, aSol: %d, aSag: %d\n", dugum, sol, sag, satir, aSol, aSag);
    if(sol > aSag || sag < aSol)
        return -1;

    if(sol >= aSol && sag <= aSag)
        return st[satir][dugum];

    int orta = (sol + sag) / 2;
    long long s1 = sorgu(dugum*2, sol, orta, satir, aSol, aSag);
    long long s2 = sorgu(dugum*2+1, orta+1, sag, satir, aSol, aSag);

    if ( (s1 != -1) && (-1 != s2) )
        return gcd2(s1, s2);
    if (s1 == -1)
        return s2;
    return s1;
}


long long calculate(int P, int Q, int U, int V) {
    /* ... */

    if (sub == 3){

        long long ekok = sorgu(1, 0, su-1, P, Q, V);

        for (int i = P+1; i <= U; i++) {
            long long s = sorgu(1, 0, su-1, i, Q, V);
            ekok = gcd2(ekok, s);
        }

        return ekok;
    }

    else {
        long long ekok;// = mat[P][Q];

        for(int i = P; i <= U; i++) {
            for(int j = Q; j <= V; j++)
                ekok = gcd2(ekok, mat[i][j]);
        }

        return ekok;
    }
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^
game.cpp: In function 'long long int calculate(int, int, int, int)':
game.cpp:86:19: warning: 'ekok' may be used uninitialized in this function [-Wmaybe-uninitialized]
         long long ekok;// = mat[P][Q];
                   ^

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41084 KB Output is correct
2 Correct 0 ms 41084 KB Output is correct
3 Correct 0 ms 41084 KB Output is correct
4 Correct 1809 ms 41084 KB Output is correct
5 Correct 903 ms 41084 KB Output is correct
6 Correct 1466 ms 41084 KB Output is correct
7 Correct 1269 ms 41084 KB Output is correct
8 Correct 1016 ms 41084 KB Output is correct
9 Correct 1479 ms 41084 KB Output is correct
10 Correct 1246 ms 41084 KB Output is correct
11 Correct 0 ms 41084 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41084 KB Output is correct
2 Correct 0 ms 41084 KB Output is correct
3 Correct 0 ms 41084 KB Output is correct
4 Correct 0 ms 41084 KB Output is correct
5 Correct 0 ms 41084 KB Output is correct
6 Correct 0 ms 41084 KB Output is correct
7 Correct 0 ms 41084 KB Output is correct
8 Correct 0 ms 41084 KB Output is correct
9 Correct 0 ms 41084 KB Output is correct
10 Correct 0 ms 41084 KB Output is correct
11 Correct 0 ms 41084 KB Output is correct
12 Execution timed out 13000 ms 41084 KB Execution timed out
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41084 KB Output is correct
2 Correct 0 ms 41084 KB Output is correct
3 Correct 0 ms 41084 KB Output is correct
4 Correct 0 ms 41084 KB Output is correct
5 Correct 0 ms 41084 KB Output is correct
6 Correct 0 ms 41084 KB Output is correct
7 Correct 0 ms 41084 KB Output is correct
8 Correct 0 ms 41084 KB Output is correct
9 Correct 0 ms 41084 KB Output is correct
10 Correct 0 ms 41084 KB Output is correct
11 Correct 0 ms 41084 KB Output is correct
12 Correct 1469 ms 41084 KB Output is correct
13 Correct 946 ms 41084 KB Output is correct
14 Correct 1476 ms 41084 KB Output is correct
15 Correct 1419 ms 41084 KB Output is correct
16 Correct 1059 ms 41084 KB Output is correct
17 Correct 1363 ms 41084 KB Output is correct
18 Correct 1116 ms 41084 KB Output is correct
19 Execution timed out 13000 ms 41084 KB Execution timed out
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41084 KB Output is correct
2 Correct 0 ms 41084 KB Output is correct
3 Correct 0 ms 41084 KB Output is correct
4 Correct 0 ms 41084 KB Output is correct
5 Correct 0 ms 41084 KB Output is correct
6 Correct 0 ms 41084 KB Output is correct
7 Correct 0 ms 41084 KB Output is correct
8 Correct 0 ms 41084 KB Output is correct
9 Correct 0 ms 41084 KB Output is correct
10 Correct 0 ms 41084 KB Output is correct
11 Correct 0 ms 41084 KB Output is correct
12 Correct 1646 ms 41084 KB Output is correct
13 Correct 936 ms 41084 KB Output is correct
14 Correct 1439 ms 41084 KB Output is correct
15 Correct 1343 ms 41084 KB Output is correct
16 Correct 1056 ms 41084 KB Output is correct
17 Correct 1516 ms 41084 KB Output is correct
18 Correct 1233 ms 41084 KB Output is correct
19 Execution timed out 13000 ms 41084 KB Execution timed out
20 Halted 0 ms 0 KB -