oj.uz

Submission #1082318

# Submission time Handle Problem Language Result Execution time Memory
1082318 2024-08-31T06:50:28 Z MMihalev The Big Prize (IOI17_prize) C++14
20 / 100
 53 ms 1728 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include "prize.h"
using namespace std;
const int MAX_N=2e5+4;
int asked[MAX_N][2];
bool used[MAX_N];
int qq;
pair<int,int>query(int pos)
{
    if(used[pos])return {asked[pos][0],asked[pos][1]};

    if(qq>10000)while(1);
    used[pos]=1;
    qq++;
    auto ve=ask(pos);
    asked[pos][0]=ve[0];
    asked[pos][1]=ve[1];
    return {ve[0],ve[1]};
}
int find_best(int n)
{
    long long N=n;
    int prevpos=-1;
    while(1)
    {
        prevpos++;
        if(prevpos>=n)break;
        auto cur=query(prevpos);
        long long all=cur.first+cur.second;
        if(all!=0)
        {
            int l=prevpos,r=n-1;
            while(l<=r)
            {
                int mid=(l+r)/2;
                auto cur2=query(mid);
                if(cur2.first==cur.first)
                {
                    prevpos=mid;
                    l=mid+1;
                }
                else r=mid-1;
            }
        }
        else
        {
            return prevpos;
        }
        cur=query(prevpos);
        all=cur.first+cur.second;
        if(all==0)return prevpos;
    }
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:25:15: warning: unused variable 'N' [-Wunused-variable]
   25 |     long long N=n;
      |               ^
prize.cpp:56:1: warning: control reaches end of non-void function [-Wreturn-type]
   56 | }
      | ^

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 3 ms 856 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 4 ms 1368 KB Output is correct
14 Correct 3 ms 344 KB Output is correct
15 Correct 10 ms 948 KB Output is correct
16 Incorrect 53 ms 1728 KB Incorrect
17 Halted 0 ms 0 KB -