oj.uz

답안 #1089697

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1089697 2024-09-16T22:28:31 Z urd05 커다란 상품 (IOI17_prize) C++17
0 / 100
 60 ms 2492 KB 
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> P;
int n;
P save[200005];

P query(int i) {
    if (save[i].first!=-1) {
        return save[i];
    }
    vector<int> got=ask(i);
    return save[i]=P(got[0],got[1]);
}

vector<int> vec;

void solve(int l,int r,int k,int y) {
    if (l>r) {
        return;
    }
    int mid=(l+r)/2;
    P got=query(mid);
    if (got.first+got.second==n-1) {
        solve(l,mid-1,y-got.second,y);
        solve(mid+1,r,k-(y-got.second),got.second);
        return;
    }
    vec.push_back(mid);
    int cnt=1;
    for(int i=mid-1;i>=l;i--) {
        P got=query(i);
        if (got.first+got.second==n-1) {
            solve(l,i-1,y-got.second,y);
            solve(mid+1,r,k-(y-got.second)-cnt,got.second-cnt);
            return;
        }
        else {
            vec.push_back(i);
            cnt++;
        }
    }
    solve(mid+1,r,k-cnt,y-cnt);
}

int find_best(int N) {
    n=N;
	for(int i = 0; i < n; i++) {
	    save[i]=P(-1,-1);
	}
	int ind=450;
	int cnt=0;
	set<int> s;
	for(int i=0;i<450;i++) {
	    P got=query(i);
	    s.insert(got.first+got.second);
	    if (s.size()==5) {
	        int mx=*s.rbegin();
	        for(int j=0;j<=i;j++) {
	            if (save[j].first+save[j].second!=mx) {
	                vec.push_back(j);
	                cnt--;
	            }
	            else {
	                cnt=save[j].second;
	            }
	        }
	        ind=i+1;
	        break;
	    }
	    if (i==449||i==n-1) {
	        ind=i+1;
	        int mx=*s.rbegin();
	        for(int j=0;j<=i;j++) {
	            if (save[j].first+save[j].second!=mx) {
	                vec.push_back(j);
	                cnt--;
	            }
	            else {
	                cnt=save[j].second;
	            }
	        }
	        break;
	    }
	}
	solve(ind,n-1,cnt,cnt);
	for(int x:vec) {
	    if (query(x)==P(0,0)) {
	        return x;
	    }
	}
	return 0;
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 2492 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 49 ms 2272 KB Incorrect
2 Halted 0 ms 0 KB -