oj.uz

Submission #235396

# Submission time Handle Problem Language Result Execution time Memory
235396 2020-05-28T08:14:57 Z crossing0ver Game (IOI13_game) C++17
37 / 100
 13000 ms 81272 KB 
#include<bits/stdc++.h>
#define ll long long
#include "game.h"
using namespace std;

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 t[100][4*100001];
ll t1[2000][2001][12];
int fr[2000][12];
int pos,l,r,sd,R,C;
ll val;
void upd (int v,int tl,int tr) {
	if (tl == tr) {
		t[sd][v] = val;
		return;
	}
	int tm = (tl + tr)/2;
	if (pos <= tm) upd(v*2,tl,tm);
	else upd(v*2|1,tm+1,tr);
	t[sd][v] = gcd2(t[sd][v*2],t[sd][v*2|1]);
}

ll get (int v,int tl,int tr) {
	if (l > tr || r < tl) return 0;
	if (l <= tl && r >= tr) {
		return t[sd][v];
	}
	int tm = (tl + tr)/2;
	return gcd2 ( get (v*2,tl,tm), get (v*2|1,tm+1,tr));
}

int i,j,c;
void update(int P, int Q, long long K) {
	sd = P;
	val = K; pos = Q;
	if (C > 2000 || R > 2000)
	upd (1,0,100000);
	else  {
		t1[P][Q][0] = K;
		for (i = Q; i < C; i++) {
			for (j = 1; j < 12 && fr[i][j-1]; j++) {
				t1[P][i][j] = gcd2(t1[P][i][j-1], t1 [P][fr[i][j-1] - 1][ j - 1]);  
			}
		}
}
}
ll s;
int sz;
long long calculate(int P, int Q, int U, int V) {
    s = 0;
    l = Q; r = V;
    if (C > 2000 || R > 2000)
    for (sd = P; sd <= U; sd++) 	
    	s = gcd2(s,get (1,0,100000));
    else 
    	for (i = P; i <= U; i++)  {
    	    sz = r - l + 1;
    		c = V;
    		for (j = 0; j < 12 && c != - 1; j++) {
    			if ((1 << j) & sz)
			s = gcd2(s,t1[i][c][j]),
			c = fr[c][j] - 1;
		}
		}
	return s;
}

void init(int R1, int C1) {R = R1; C = C1;
for (int i = 0; i < 2000; i++) fr[i][0] = i,fr[i][1] = (i ? i - 1 : 0);
for (int i = 0; i < 2000; i++)
{
for (int j = 2; j < 12 && fr[i][j - 1]; j++)  fr[i][j] = fr [ (fr[i][ j - 1]) - 1][j-1];
}
}

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:63:5: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
     else 
     ^~~~
game.cpp:73:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
  return s;
  ^~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 1083 ms 24916 KB Output is correct
5 Correct 656 ms 25080 KB Output is correct
6 Correct 821 ms 25720 KB Output is correct
7 Correct 874 ms 25336 KB Output is correct
8 Correct 708 ms 24056 KB Output is correct
9 Correct 835 ms 25464 KB Output is correct
10 Correct 747 ms 24824 KB Output is correct
11 Correct 5 ms 384 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 5 ms 768 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Execution timed out 13052 ms 81272 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 6 ms 1024 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 6 ms 1024 KB Output is correct
10 Correct 5 ms 768 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 1069 ms 24792 KB Output is correct
13 Correct 652 ms 24952 KB Output is correct
14 Correct 825 ms 25612 KB Output is correct
15 Correct 863 ms 25336 KB Output is correct
16 Correct 702 ms 24184 KB Output is correct
17 Correct 859 ms 25336 KB Output is correct
18 Correct 775 ms 24928 KB Output is correct
19 Execution timed out 13063 ms 80972 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 5 ms 768 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 1012 ms 24712 KB Output is correct
13 Correct 681 ms 25080 KB Output is correct
14 Correct 838 ms 25852 KB Output is correct
15 Correct 845 ms 25212 KB Output is correct
16 Correct 706 ms 23928 KB Output is correct
17 Correct 858 ms 25332 KB Output is correct
18 Correct 810 ms 25040 KB Output is correct
19 Execution timed out 13014 ms 80856 KB Time limit exceeded
20 Halted 0 ms 0 KB -