oj.uz

답안 #1029241

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1029241 2024-07-20T14:13:40 Z amirhoseinfar1385 커다란 상품 (IOI17_prize) C++17
0 / 100
 1 ms 344 KB 
#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
map<int,pair<int,int>>mp;
int cnta=0;

pair<int,int>pors(int u){
	if(mp.count(u)==0){
		cnta++;
		if(cnta>=10000){
			exit(23);
		}
		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;
	int wtf=-1;
	vector<int>allz;
	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;
		if(wtf!=-1){
			fake=pors(wtf);
			if(av.first+av.second<=fake.first+fake.second){
				i++;
				allz.push_back(i);
				continue;
			}
		}
		int low=i,high=n,mid,f=0;
		for(auto x:mp){
			mid=x.first;
			fake=pors(mid);
			if(fake.first+fake.second!=av.first+av.second){
				if(fake.first+fake.second>av.first+av.second){
					f=1;
					break;
				}
				high=mid;
			}else{
				if(fake.first-av.first==0){
					low=mid;
					high=n;
				}else{
					high=mid;
				}
			}
		}
		if(f){
			allz.push_back(i);
			wtf=i;
			i=low+1;
			continue;
		}
		low=max(low,i);
		while(high-low>1){
			mid=(high+low)>>1;
			fake=pors(mid);
			if(fake.first+fake.second!=av.first+av.second){
				if(fake.first+fake.second>av.first+av.second){
					wtf=i;
					allz.push_back(i);
					break;
				}else{
					pair<int,int>fakea;
					for(int j=(int)allz.back()-1;j>=0;j--){
						fakea=pors(allz[j]);
						if(fake.first+fake.second==fakea.first+fakea.second){
							if(fake.first-fakea.first>0){
								high=mid;
							}else{
								low=mid;
							}
							break;
						}
					}
				}
				//high=mid;
			}else{
				if(fake.first-av.first==0){
					low=mid;
				}else{
					high=mid;
				}
			}
		}
		i=low+1;
	}
	return 0;
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -