oj.uz

Submission #1029105

# Submission time Handle Problem Language Result Execution time Memory
1029105 2024-07-20T12:27:41 Z amirhoseinfar1385 The Big Prize (IOI17_prize) C++17
20 / 100
 365 ms 1168 KB 
#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
map<int,pair<int,int>>mp;

pair<int,int>pors(int u){
	if(mp.count(u)==0){
		vector<int>hey=ask(u);
		mp[u]=make_pair(hey[0],hey[1]);
	}
	return mp[u];
}

int find_best(int n) {
	mp.clear();
	int cnta=0;
	for(int i=0;i<n;){
		//cout<<i<<endl;
		pair<int,int>av=pors(i);
		if(av.first+av.second==0){
			return i;
		}
		cnta++;
		pair<int,int>fake;
		int low=i,high=n,mid;
		for(auto x:mp){
			mid=x.first;
			fake=pors(mid);
			if(fake.first+fake.second!=av.first+av.second){
				high=mid;
			}else{
				if(fake.first-av.first==0){
					low=mid;
				}else{
					high=mid;
				}
			}
		}
		low=max(low,i);
		high=n;
		while(high-low>1){
			mid=(high+low)>>1;
			fake=pors(mid);
			if(fake.first+fake.second!=av.first+av.second){
				high=mid;
			}else{
				if(fake.first-av.first==0){
					low=mid;
				}else{
					high=mid;
				}
			}
		}
		i=low+1;
	}
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 428 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 424 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 428 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 5 ms 344 KB Output is correct
14 Correct 5 ms 344 KB Output is correct
15 Correct 21 ms 524 KB Output is correct
16 Incorrect 365 ms 1168 KB Incorrect
17 Halted 0 ms 0 KB -