oj.uz

Submission #52475

# Submission time Handle Problem Language Result Execution time Memory
52475 2018-06-26T05:23:44 Z 김세빈(#1365) Secret (JOI14_secret) C++11
0 / 100
 637 ms 4700 KB 
#include "secret.h"

#include <bits/stdc++.h>

using namespace std;

vector <int> V[3030];
int S[3030];
int sz;

void Init(int N, int A[])
{
	int i,k,t;
	
	for(sz=1;sz<N;sz<<=1);
	
	for(i=0;i<N;i++) S[sz+i] = A[i];
	for(;i<sz;i++) S[sz+i] = -1;
	
	for(i=sz-1;i;i--){
		if(S[i<<1|1] == -1) S[i] = -1;
		else S[i] = Secret(S[i<<1], S[i<<1|1]);
	}
	
	for(i=1;i<sz+N;i++){
		if(~i & 1) continue;
		
		t = S[i];
		V[i].push_back(t);
		
		if(!(i & i+1)) continue;
		
		for(k=i+1>>1;;){
			if(S[k] == -1) break;
			
			if(!(k & k+1)) break;
			
			if(k & 1){
				t = Secret(t, S[k]);
				V[i].push_back(t);
			}
			
			k = k+1 >> 1;
		}
	}
	
	for(i=1;i<sz+N;i++){
		if(i & 1) continue;
		
		t = S[i];
		V[i].push_back(t);
		
		if(!(i & i-1)) continue;
		
		for(k=i-1>>1;;){
			if(S[k] == -1) break;
			
			if(!(k & k-1)) break;
			
			if(~k & 1){
				t = Secret(S[k], t);
				V[i].push_back(t);
			}
			
			k = k-1 >> 1;
		}
	}
}

int Query(int L, int R)
{
	int f1, f2, cnt1, cnt2;
	
	f1 = f2 = -1;
	cnt1 = cnt2 = 0;
	L += sz, R += sz;
	
	for(;L<R;){
		
		if(L & 1){
			if(f1 == -1) f1 = L;
			else cnt1 ++;
		}
		if(~R & 1){
			if(f2 == -1) f2 = R;
			else cnt2 ++;
		}
		
		L = L+1 >> 1;
		R = R-1 >> 1;
	}
	
	if(L == R){
		if(f1 == -1 && f2 == -1) return S[L];
		else if(f1 == -1) return Secret(S[L], V[f2][cnt2]);
		else if(f2 == -1) return Secret(V[f1][cnt1], S[R]);
		else if(L & 1) return Secret(V[f1][cnt1+1], V[f2][cnt2]);
		else return Secret(V[f1][cnt1], V[f2][cnt2+1]);
	}
	
	return Secret(V[f1][cnt1], V[f2][cnt2]);
}

Compilation message

secret.cpp: In function 'void Init(int, int*)':
secret.cpp:31:13: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   if(!(i & i+1)) continue;
            ~^~
secret.cpp:33:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   for(k=i+1>>1;;){
         ~^~
secret.cpp:36:14: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
    if(!(k & k+1)) break;
             ~^~
secret.cpp:43:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    k = k+1 >> 1;
        ~^~
secret.cpp:53:13: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   if(!(i & i-1)) continue;
            ~^~
secret.cpp:55:10: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   for(k=i-1>>1;;){
         ~^~
secret.cpp:58:14: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
    if(!(k & k-1)) break;
             ~^~
secret.cpp:65:9: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
    k = k-1 >> 1;
        ~^~
secret.cpp: In function 'int Query(int, int)':
secret.cpp:89:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   L = L+1 >> 1;
       ~^~
secret.cpp:90:8: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   R = R-1 >> 1;
       ~^~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 2424 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 173 ms 2664 KB Output is correct - number of calls to Secret by Init = 3093, maximum number of calls to Secret by Query = 1
3 Correct 196 ms 2736 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Incorrect 637 ms 4536 KB Wrong Answer [1]
5 Incorrect 588 ms 4576 KB Wrong Answer [1]
6 Incorrect 587 ms 4648 KB Wrong Answer [1]
7 Incorrect 583 ms 4700 KB Wrong Answer [1]
8 Incorrect 593 ms 4700 KB Wrong Answer [1]
9 Incorrect 584 ms 4700 KB Wrong Answer [1]
10 Incorrect 584 ms 4700 KB Wrong Answer [1]