oj.uz

답안 #1041256

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1041256 2024-08-01T19:50:02 Z PCTprobability 커다란 상품 (IOI17_prize) C++17
0 / 100
 0 ms 344 KB 
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int ans;
int m;
int N;
vector<int> query(int id){
  cout<<id<<endl;
  if(id==N) return {m,0};
  else{
    vector<int> a=ask(id);
    if(a[0]+a[1]==0) ans=id;
    return a;
  }
}
void solve(int l,int r,int x,int p,int q){
  if(x==0) return;
  if(r-l+1==x){
    for(int i=l;i<=r;i++){
      vector<int> a=query(i);
      if(a[0]+a[1]==0){
        ans=i;
        return;
      }
    }
    return;
  }
  int mid=(l+r)/2;
  //mid+1 を聞く
  vector<int> a=query(mid+1);
  if(a[0]+a[1]==m){
    solve(l,mid,a[0]-p,p,a[1]);
    solve(mid+1,r,a[1]-q,a[0],q);
  }
  else{
    int now=mid+1;
    int cnt=1;
    while(now<r){
      vector<int> a=query(now+1);
      if(a[0]+a[1]!=m){
        cnt++;
        now++;
      }
      else{
        break;
      }
    }
    if(now==r){
      //mid+1 から r は全部特殊
      solve(l,mid,x-cnt,p,q+cnt);
    }
    else{
      vector<int> a=query(now+1);
      //mid+1 から now は全部特殊
      solve(l,mid,a[0]-cnt-p,p,a[1]+cnt);
      solve(now+1,r,a[1]-q,a[0],q);
    }
  }
}
int find_best(int n) {
  N=n;
  if(n<=5000){
    for(int i=0;i<n;i++){
      vector<int> a=ask(i);
      if(a[0]+a[1]==0) return i;
    }
  }
  m=-1;
  for(int i=0;i<30;i++){
    int k=rand()%n;
    vector<int> a=query(k);
    if(a[0]+a[1]==0) return i;
    if(m<a[0]+a[1]) m=a[0]+a[1];
  }
  solve(0,n-1,m,0,0);
  return ans;
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Token "89383" doesn't correspond to pattern "[A-B]{1}"
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Token "89383" doesn't correspond to pattern "[A-B]{1}"
2 Halted 0 ms 0 KB -