oj.uz

Submission #940049

# Submission time Handle Problem Language Result Execution time Memory
940049 2024-03-07T04:46:32 Z Wansur The Big Prize (IOI17_prize) C++17
20 / 100
 44 ms 600 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'

std::vector<int> ask(int i);
typedef long long ll;
using namespace std;

struct seg{
    int m1,m2,sum,cnt;
};

const string out[2]={"NO\n","YES\n"};
const ll dx[]={0,1,0,-1,-1,1,1,-1};
const ll dy[]={1,0,-1,0,-1,1,-1,1};
const int mod=998244353;
const int md=1e9+7;
//const int mx=2e5+12;

const bool T=0;

int cnt=0;
int answer=-1;
int mx;

vector<int> Ask(int i){
    cnt++;
    if(cnt==10000){
        assert(0);
    }
    return ask(i);
}

void find(int l,int r){
    if(l>r)return;
    if(l==r){
        auto v=Ask(l);
        if(v[0]+v[1]==0){
            answer=l;
            return;
        }
    }
    int mid=l+r>>1;
    auto v=Ask(mid);
    if(v[0]+v[1]<mx){
        if(v[0]+v[1]==0){
            answer=mid;
            return;
        }
        mx=v[0]+v[1];
        if(v[0]>0)find(l,mid-1);
        if(answer!=-1)return;
        if(v[1]>0)find(mid+1,r);
        if(answer!=-1)return;
    }
    else{
        if(v[0]>0){
            find(l, mid-1);
            if(answer!=-1)return;
        }
        if(v[1]>0){
            find(mid+1, r);
            if(answer!=-1)return;
        }
    }
}

int find_best(int n){
    int pos=0;
    auto ma=ask(0);
    if(ma[0]+ma[1]==0){
        return 0;
    }
    for(int i=1;i<min(550,n);i++){
        auto v=Ask(i);
        if(v[0]+v[1]<ma[0]+ma[1]){
            ma=v;
            pos=i;
        }
        if(v[0]+v[1]==0){
            return i;
        }
    }
    mx=ma[0]+ma[1];
    find(550, n-1);
    return answer;
}

Compilation message

prize.cpp: In function 'void find(int, int)':
prize.cpp:44:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     int mid=l+r>>1;
      |             ~^~
prize.cpp: In function 'int find_best(int)':
prize.cpp:70:9: warning: variable 'pos' set but not used [-Wunused-but-set-variable]
   70 |     int pos=0;
      |         ^~~

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 2 ms 544 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Runtime error 44 ms 412 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -