oj.uz

답안 #56491

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
56491 2018-07-11T13:12:31 Z Kerim 커다란 상품 (IOI17_prize) C++17
90 / 100
 106 ms 572 KB 
#include "bits/stdc++.h"
#include "prize.h"
#define MAXN 200009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
#define left cep
#define right sag
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<=b){a=b;return 1;}return 0;}
int n;
const int c=480;
//~ int arr[MAXN],query=0;
//~ int left[MAXN],right[MAXN],cnt[123];
//~ vector<int>ask(int x){
	//~ query++;
	//~ vector<int>res(2,0);
	//~ assert(res[0]+res[1]==0);
	//~ res[0]=left[x];
	//~ res[1]=right[x];
	//~ return res;	
//~ }
int find_best(int N){
	n=N;
	int mx=0;
	vector<int>res,tmp;
	for(int i=0;i<min(n,c);i++){
		res=ask(i);
		if(res[0]+res[1]==0)
			return i;
		umax(mx,res[0]+res[1]);
	}
	for(int i=c;i<n;i+=c){
		int who=i;
		while(who<min(n,i+c) ){
			tmp=ask(who);
			if(tmp[0]+tmp[1]==0)
				return who;
			if(tmp[0]+tmp[1]<mx){
				who++;
				continue;
			}	
			int st=who+1,en=min(n-1,i+c-1),pos=who;
			while(st<=en){
				int mid=(st+en)/2;
				res=ask(mid);
				if(res!=tmp)
					en=mid-1;
				else{
					pos=mid;
					st=mid+1;
				}	
			}
			who=pos+1;
		}
	}
	//~ while(who<n){
		//~ tmp=ask(who);
		//~ if(tmp[0]+tmp[1]==0)
			//~ return who;
		//~ if(tmp[0]+tmp[1]<mx){
			//~ who++;
			//~ continue;
		//~ }	
		//~ int st=who+1,en=n-1,pos=who;
		//~ while(st<=en){
			//~ int mid=(st+en)/2;
			//~ res=ask(mid);
			//~ if(res!=tmp)
				//~ en=mid-1;
			//~ else{
				//~ pos=mid;
				//~ st=mid+1;
			//~ }	
		//~ }
		//~ who=pos+1;
	//~ }
	return -1;
}
//~ int main(){
    //~ freopen("file.in", "r", stdin);
    //~ int N;
    //~ scanf("%d",&N);
    //~ for(int i=0;i<N;i++)
		//~ scanf("%d",arr+i);
	//~ for(int i=0;i<N;i++){
		//~ for(int j=1;j<arr[i];j++)
			//~ left[i]+=cnt[j];
		//~ cnt[arr[i]]++;	
	//~ }	
	//~ memset(cnt,0,sizeof cnt);
	//~ for(int i=N-1;i>=0;i--){
		//~ for(int j=1;j<arr[i];j++)
			//~ right[i]+=cnt[j];
		//~ cnt[arr[i]]++;	
	//~ }
	//~ int ans=find_best(N);
	//~ assert(arr[ans]==1);
	//~ printf("%d\n",ans);	
	//~ debug(query);
	//~ return 0;
//~ }

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 248 KB Output is correct
2 Correct 33 ms 436 KB Output is correct
3 Correct 26 ms 436 KB Output is correct
4 Correct 52 ms 436 KB Output is correct
5 Correct 23 ms 528 KB Output is correct
6 Correct 2 ms 528 KB Output is correct
7 Correct 24 ms 528 KB Output is correct
8 Correct 30 ms 528 KB Output is correct
9 Correct 21 ms 528 KB Output is correct
10 Correct 36 ms 528 KB Output is correct

Subtask #2
70.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 528 KB Output is correct
2 Correct 26 ms 536 KB Output is correct
3 Correct 24 ms 536 KB Output is correct
4 Correct 48 ms 536 KB Output is correct
5 Correct 24 ms 536 KB Output is correct
6 Correct 3 ms 536 KB Output is correct
7 Correct 26 ms 536 KB Output is correct
8 Correct 19 ms 536 KB Output is correct
9 Correct 25 ms 548 KB Output is correct
10 Correct 49 ms 548 KB Output is correct
11 Correct 25 ms 556 KB Output is correct
12 Correct 7 ms 556 KB Output is correct
13 Correct 56 ms 556 KB Output is correct
14 Correct 9 ms 556 KB Output is correct
15 Correct 21 ms 556 KB Output is correct
16 Partially correct 93 ms 556 KB Partially correct - number of queries: 7731
17 Correct 8 ms 556 KB Output is correct
18 Partially correct 96 ms 556 KB Partially correct - number of queries: 9254
19 Correct 6 ms 556 KB Output is correct
20 Correct 26 ms 556 KB Output is correct
21 Correct 35 ms 556 KB Output is correct
22 Correct 14 ms 556 KB Output is correct
23 Correct 11 ms 556 KB Output is correct
24 Correct 9 ms 556 KB Output is correct
25 Partially correct 55 ms 556 KB Partially correct - number of queries: 5259
26 Partially correct 25 ms 556 KB Partially correct - number of queries: 5120
27 Correct 18 ms 556 KB Output is correct
28 Partially correct 90 ms 556 KB Partially correct - number of queries: 8784
29 Partially correct 61 ms 556 KB Partially correct - number of queries: 7340
30 Partially correct 71 ms 560 KB Partially correct - number of queries: 9233
31 Correct 4 ms 560 KB Output is correct
32 Correct 35 ms 560 KB Output is correct
33 Correct 2 ms 560 KB Output is correct
34 Correct 32 ms 560 KB Output is correct
35 Correct 19 ms 560 KB Output is correct
36 Correct 23 ms 560 KB Output is correct
37 Correct 12 ms 560 KB Output is correct
38 Correct 7 ms 560 KB Output is correct
39 Correct 42 ms 560 KB Output is correct
40 Partially correct 90 ms 560 KB Partially correct - number of queries: 8555
41 Partially correct 39 ms 560 KB Partially correct - number of queries: 5499
42 Partially correct 32 ms 560 KB Partially correct - number of queries: 5499
43 Partially correct 24 ms 560 KB Partially correct - number of queries: 5046
44 Correct 17 ms 560 KB Output is correct
45 Correct 47 ms 560 KB Output is correct
46 Correct 5 ms 560 KB Output is correct
47 Correct 25 ms 560 KB Output is correct
48 Partially correct 49 ms 560 KB Partially correct - number of queries: 6722
49 Correct 22 ms 560 KB Output is correct
50 Partially correct 57 ms 560 KB Partially correct - number of queries: 9251
51 Correct 39 ms 560 KB Output is correct
52 Correct 7 ms 560 KB Output is correct
53 Correct 45 ms 560 KB Output is correct
54 Correct 30 ms 560 KB Output is correct
55 Correct 3 ms 560 KB Output is correct
56 Partially correct 106 ms 560 KB Partially correct - number of queries: 9238
57 Partially correct 72 ms 560 KB Partially correct - number of queries: 6632
58 Partially correct 57 ms 560 KB Partially correct - number of queries: 6685
59 Partially correct 36 ms 560 KB Partially correct - number of queries: 5499
60 Partially correct 40 ms 560 KB Partially correct - number of queries: 5120
61 Correct 32 ms 560 KB Output is correct
62 Correct 8 ms 560 KB Output is correct
63 Correct 20 ms 560 KB Output is correct
64 Correct 34 ms 560 KB Output is correct
65 Correct 44 ms 560 KB Output is correct
66 Partially correct 48 ms 560 KB Partially correct - number of queries: 5098
67 Correct 43 ms 560 KB Output is correct
68 Correct 4 ms 560 KB Output is correct
69 Partially correct 52 ms 560 KB Partially correct - number of queries: 5081
70 Correct 50 ms 560 KB Output is correct
71 Partially correct 83 ms 560 KB Partially correct - number of queries: 9296
72 Correct 37 ms 560 KB Output is correct
73 Partially correct 77 ms 560 KB Partially correct - number of queries: 9233
74 Partially correct 75 ms 560 KB Partially correct - number of queries: 9260
75 Correct 45 ms 560 KB Output is correct
76 Partially correct 53 ms 560 KB Partially correct - number of queries: 8630
77 Partially correct 85 ms 560 KB Partially correct - number of queries: 9281
78 Correct 39 ms 560 KB Output is correct
79 Partially correct 76 ms 560 KB Partially correct - number of queries: 6717
80 Partially correct 88 ms 560 KB Partially correct - number of queries: 9268
81 Partially correct 89 ms 560 KB Partially correct - number of queries: 9278
82 Partially correct 53 ms 560 KB Partially correct - number of queries: 9228
83 Correct 47 ms 560 KB Output is correct
84 Partially correct 85 ms 560 KB Partially correct - number of queries: 8426
85 Partially correct 47 ms 560 KB Partially correct - number of queries: 9245
86 Correct 24 ms 560 KB Output is correct
87 Correct 33 ms 560 KB Output is correct
88 Correct 35 ms 560 KB Output is correct
89 Correct 51 ms 572 KB Output is correct
90 Correct 44 ms 572 KB Output is correct
91 Correct 36 ms 572 KB Output is correct
92 Correct 39 ms 572 KB Output is correct
93 Correct 44 ms 572 KB Output is correct
94 Correct 40 ms 572 KB Output is correct
95 Correct 45 ms 572 KB Output is correct
96 Correct 35 ms 572 KB Output is correct
97 Correct 29 ms 572 KB Output is correct