oj.uz

답안 #949642

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
949642 2024-03-19T14:01:59 Z qin 커다란 상품 (IOI17_prize) C++17
93.46 / 100
 37 ms 608 KB 
#include <bits/stdc++.h>
#include "prize.h"
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1;
//~ #ifdef LOCAL
//~ vector<int> ask(int i){ return vector<int>(2, 0); }
//~ #endif
int SUM; // bound na checka, czy to jest gosc z lepszej, czy nie
int f(int l, int r, int resl, int resr){
		//~ printf("%d %d\n", l, r);
		int midl = (l+r)/2, midr = (l+r)/2;
		int result = 0;
		
		vv<int> tmp = ask(midl), tmp2 = tmp; int sum = tmp[0]+tmp[1];
		while(sum != SUM && l < midl-1){
				if(!sum){ return midl;}
				--midl;
				tmp = ask(midl); sum = tmp[0]+tmp[1];
		}
		if(!sum) return midl;
		if(sum == SUM && resl != tmp[0]) result = max(result, f(l, midl, resl, tmp[0]));
		
		sum = tmp2[0]+tmp2[1];
		while(sum != SUM && midr+1 < r){
				if(!sum) return midr;
				++midr;
				tmp = ask(midr); sum = tmp[0]+tmp[1];
		}
		if(!sum) return midr;
		if(sum == SUM && resr != tmp[0]) result = max(result, f(midr, r, tmp[0], resr));
		
		return result;
}
int find_best(int n){
		//~ if(n <= 5000){
				//~ vv<int> tmp; int result = 0;
				//~ for(int i = 0; i < n; ++i){
						//~ tmp = ask(i);
						//~ if(!(tmp[0]+tmp[1])){ result = i; break; }
				//~ } return result;
		//~ }
		int sq = 2*int(sqrt(n));
		for(int i = 0; i < sq; ++i){
				vv<int> tmp = ask(i); int sum = tmp[0]+tmp[1];
				SUM = max(SUM, sum);
				if(!sum) return i;
		}
		int l = 0, r = n-1, resl = 0, resr = 0;
		vv<int> tmp;
		for(int i = 0; i < n; ++i){
				tmp = ask(i); int sum = tmp[0]+tmp[1];
				if(sum == SUM){ l = i, resl = tmp[0]; break; }
				else if(!sum) return i;
		}
		for(int i = n-1; ~i; --i){
				tmp = ask(i); int sum = tmp[0]+tmp[1];
				if(sum == SUM){ r = i, resr = tmp[0]; break; }
				else if(!sum) return i;
		}
		return f(l, r, resl, resr);
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 432 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 516 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 0 ms 428 KB Output is correct
7 Correct 3 ms 436 KB Output is correct
8 Correct 5 ms 340 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 4 ms 428 KB Output is correct

Subtask #2
73.46 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 4 ms 436 KB Output is correct
3 Correct 7 ms 432 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 4 ms 344 KB Output is correct
11 Correct 7 ms 432 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 6 ms 428 KB Output is correct
14 Correct 5 ms 344 KB Output is correct
15 Partially correct 24 ms 424 KB Partially correct - number of queries: 5292
16 Partially correct 33 ms 440 KB Partially correct - number of queries: 5545
17 Correct 3 ms 600 KB Output is correct
18 Partially correct 34 ms 436 KB Partially correct - number of queries: 5516
19 Correct 2 ms 344 KB Output is correct
20 Correct 16 ms 432 KB Output is correct
21 Partially correct 23 ms 344 KB Partially correct - number of queries: 5505
22 Correct 24 ms 436 KB Output is correct
23 Correct 4 ms 432 KB Output is correct
24 Correct 6 ms 344 KB Output is correct
25 Partially correct 31 ms 344 KB Partially correct - number of queries: 5136
26 Partially correct 29 ms 344 KB Partially correct - number of queries: 5103
27 Correct 5 ms 432 KB Output is correct
28 Partially correct 21 ms 432 KB Partially correct - number of queries: 5022
29 Correct 19 ms 344 KB Output is correct
30 Partially correct 23 ms 344 KB Partially correct - number of queries: 5490
31 Correct 2 ms 544 KB Output is correct
32 Correct 7 ms 432 KB Output is correct
33 Correct 0 ms 592 KB Output is correct
34 Partially correct 24 ms 344 KB Partially correct - number of queries: 5527
35 Correct 8 ms 436 KB Output is correct
36 Partially correct 21 ms 600 KB Partially correct - number of queries: 5459
37 Correct 5 ms 600 KB Output is correct
38 Correct 5 ms 596 KB Output is correct
39 Partially correct 30 ms 340 KB Partially correct - number of queries: 5462
40 Correct 23 ms 344 KB Output is correct
41 Partially correct 27 ms 432 KB Partially correct - number of queries: 5505
42 Partially correct 23 ms 344 KB Partially correct - number of queries: 5505
43 Partially correct 29 ms 344 KB Partially correct - number of queries: 5407
44 Partially correct 24 ms 432 KB Partially correct - number of queries: 5529
45 Partially correct 19 ms 344 KB Partially correct - number of queries: 5116
46 Correct 2 ms 344 KB Output is correct
47 Partially correct 23 ms 608 KB Partially correct - number of queries: 5178
48 Partially correct 37 ms 344 KB Partially correct - number of queries: 5502
49 Partially correct 23 ms 344 KB Partially correct - number of queries: 5496
50 Partially correct 24 ms 344 KB Partially correct - number of queries: 5525
51 Partially correct 24 ms 344 KB Partially correct - number of queries: 5517
52 Partially correct 30 ms 344 KB Partially correct - number of queries: 5534
53 Correct 5 ms 432 KB Output is correct
54 Partially correct 26 ms 344 KB Partially correct - number of queries: 5498
55 Correct 2 ms 344 KB Output is correct
56 Partially correct 22 ms 344 KB Partially correct - number of queries: 5497
57 Partially correct 36 ms 344 KB Partially correct - number of queries: 5496
58 Partially correct 30 ms 344 KB Partially correct - number of queries: 5507
59 Partially correct 28 ms 432 KB Partially correct - number of queries: 5514
60 Partially correct 30 ms 344 KB Partially correct - number of queries: 5457
61 Correct 4 ms 344 KB Output is correct
62 Correct 4 ms 600 KB Output is correct
63 Correct 4 ms 344 KB Output is correct
64 Correct 4 ms 440 KB Output is correct
65 Correct 4 ms 344 KB Output is correct
66 Correct 5 ms 344 KB Output is correct
67 Correct 10 ms 344 KB Output is correct
68 Correct 2 ms 344 KB Output is correct
69 Correct 5 ms 344 KB Output is correct
70 Correct 5 ms 344 KB Output is correct
71 Partially correct 24 ms 344 KB Partially correct - number of queries: 5654
72 Correct 7 ms 436 KB Output is correct
73 Partially correct 26 ms 344 KB Partially correct - number of queries: 5591
74 Partially correct 26 ms 344 KB Partially correct - number of queries: 5618
75 Correct 5 ms 344 KB Output is correct
76 Partially correct 28 ms 344 KB Partially correct - number of queries: 5006
77 Partially correct 27 ms 344 KB Partially correct - number of queries: 5635
78 Correct 6 ms 432 KB Output is correct
79 Correct 13 ms 344 KB Output is correct
80 Partially correct 25 ms 344 KB Partially correct - number of queries: 5605
81 Partially correct 28 ms 540 KB Partially correct - number of queries: 5643
82 Partially correct 24 ms 344 KB Partially correct - number of queries: 5564
83 Correct 4 ms 344 KB Output is correct
84 Correct 23 ms 436 KB Output is correct
85 Partially correct 21 ms 344 KB Partially correct - number of queries: 5653
86 Correct 6 ms 432 KB Output is correct
87 Correct 4 ms 344 KB Output is correct
88 Correct 8 ms 344 KB Output is correct
89 Correct 7 ms 432 KB Output is correct
90 Correct 5 ms 344 KB Output is correct
91 Correct 6 ms 432 KB Output is correct
92 Correct 5 ms 344 KB Output is correct
93 Correct 7 ms 436 KB Output is correct
94 Correct 6 ms 432 KB Output is correct
95 Correct 8 ms 436 KB Output is correct
96 Correct 6 ms 436 KB Output is correct
97 Correct 5 ms 340 KB Output is correct