oj.uz

답안 #52476

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
52476 2018-06-26T05:25:59 Z 김세빈(#1365) 비밀 (JOI14_secret) C++11
100 / 100
 669 ms 4720 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(S[i] == -1 || ~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(S[i] == -1 || 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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 183 ms 2552 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 190 ms 2564 KB Output is correct - number of calls to Secret by Init = 3093, maximum number of calls to Secret by Query = 1
3 Correct 177 ms 2596 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 602 ms 4464 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
5 Correct 618 ms 4584 KB Output is correct - number of calls to Secret by Init = 7008, maximum number of calls to Secret by Query = 1
6 Correct 621 ms 4720 KB Output is correct - number of calls to Secret by Init = 7008, maximum number of calls to Secret by Query = 1
7 Correct 641 ms 4720 KB Output is correct - number of calls to Secret by Init = 7008, maximum number of calls to Secret by Query = 1
8 Correct 669 ms 4720 KB Output is correct - number of calls to Secret by Init = 7008, maximum number of calls to Secret by Query = 1
9 Correct 612 ms 4720 KB Output is correct - number of calls to Secret by Init = 7008, maximum number of calls to Secret by Query = 1
10 Correct 612 ms 4720 KB Output is correct - number of calls to Secret by Init = 7008, maximum number of calls to Secret by Query = 1