oj.uz

Submission #1082713

# Submission time Handle Problem Language Result Execution time Memory
1082713 2024-09-01T09:39:04 Z MMihalev The Big Prize (IOI17_prize) C++14
20 / 100
 1000 ms 10100 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>
#include "prize.h"
using namespace std;
const int MAX_N=2e5+4;
int asked[MAX_N][2];
bool used[MAX_N];
set<int>kinds;
set<int>idx[MAX_N];
pair<int,int>query(int pos)
{
    if(used[pos])return {asked[pos][0],asked[pos][1]};

    used[pos]=1;
    auto ve=ask(pos);
    asked[pos][0]=ve[0];
    asked[pos][1]=ve[1];
    kinds.insert(ve[0]+ve[1]);
    idx[ve[0]+ve[1]].insert(pos);
    return {ve[0],ve[1]};
}
bool useless(int l,int r)
{
    for(int x:kinds)
    {
        auto it1=idx[x].lower_bound(l);
        auto it2=idx[x].upper_bound(r);
        if(it1!=idx[x].begin() && it2!=idx[x].end())
        {
            it1--;
            int pos1=(*it1);
            int pos2=(*it2);
            if(query(pos2).first-query(pos1).first==0)return 1;
        }
    }
    return 0;
}
int ans=-1;
void rec(int l,int r)
{
    if(ans!=-1)return;
    int mid=(l+r)/2;
    auto cur=query(mid);
    if(cur.first+cur.second==0){ans=mid;return;}
    if(!useless(l,mid-1))rec(l,mid-1);
    if(!useless(mid+1,r))rec(mid+1,r);
}

int find_best(int n)
{
    int prevpos=-1;
    int qq=480;
    while(qq--)
    {
        prevpos++;
        auto cur=query(prevpos);
        int all=cur.first+cur.second;
        if(all==0)return prevpos;
    }
    prevpos++;
    rec(prevpos,n-1);
    return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9816 KB Output is correct
2 Correct 9 ms 9860 KB Output is correct
3 Correct 6 ms 9816 KB Output is correct
4 Correct 7 ms 9816 KB Output is correct
5 Correct 9 ms 9816 KB Output is correct
6 Correct 4 ms 9816 KB Output is correct
7 Correct 8 ms 9816 KB Output is correct
8 Correct 10 ms 10100 KB Output is correct
9 Correct 7 ms 9816 KB Output is correct
10 Correct 6 ms 9816 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9816 KB Output is correct
2 Correct 5 ms 9816 KB Output is correct
3 Correct 5 ms 9816 KB Output is correct
4 Correct 7 ms 9856 KB Output is correct
5 Correct 8 ms 9840 KB Output is correct
6 Correct 4 ms 9816 KB Output is correct
7 Correct 6 ms 9816 KB Output is correct
8 Correct 7 ms 9816 KB Output is correct
9 Correct 6 ms 9816 KB Output is correct
10 Correct 6 ms 9816 KB Output is correct
11 Execution timed out 3022 ms 9816 KB Time limit exceeded
12 Halted 0 ms 0 KB -