Submission #525910

#	Time	Username	Problem	Language	Result	Execution time	Memory
525910		leaked	The Big Prize (IOI17_prize)	C++14	20 / 100	74 ms	1168 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>


#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define m_p make_pair
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
//#define pragma optimize("unroll-loops")
using namespace std;
const int N=2e5+1;
typedef pair<int,int> pii;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}

int find_best(int n) {
    int i=0;
    map<int,vec<int>> mp;
    mp[0]=ask(0);
    vec<int> looking={0,0};
    int q=0;
    while(i<n && 5000-q<n-i){
//        if(q>5000)
//            assert(false);
        assert(mp.count(i));
        vec<int>need=mp[i];
        ++q;
        if(need[0]==0 && need[1]==0)
            return i;
        int l=i+1,r=n;
        while(l!=r){
            int tm=(l+r)>>1;
            mp[tm]=ask(tm);
            if(mp[tm]==looking){
                return tm;
            }
            ++q;
            if(need==mp[tm]) l=tm+1;
            else r=tm;
        }
//        if(need[0]=)
        i=l;
    }
    for(int j=i;j<n;j++){
        vec<int> need=ask(j);
        if(need[0]==need[1] && need[0]==0){
            return j;
        }
    }
    return -1;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80