Submission #790809

#	Time	Username	Problem	Language	Result	Execution time	Memory
790809		peteza	The Big Prize (IOI17_prize)	C++14	90 / 100	81 ms	696 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;

bool vis[200005];

int find_best(int n) {
    if(n == 1) return 0;
    int mx = -1, ci;
    int c0, c1;
    for(int i=0;i<min(n, 500);i++) {
        auto e = ask(i);
        if(e[0] + e[1] > mx) {
            c0 = e[0], c1=e[1];
            mx = e[0] + e[1]; ci = i;
        } 
    }
    //start at ci
    int l, r, mid;
    while(1) {
        l = ci; r = n-1;
        while(l<=r) {
            mid = (l+r) >> 1;
            auto e = ask(mid);
            if(e[0] + e[1] != mx) r = mid-1;
            else if(e[0] == c0) l = mid+1;
            else r = mid - 1;
        }
        for(int i=ci;i<l;i++) 
            vis[i] = 1;
        if(l >= n-1) break;
        ci = l; auto e = ask(ci);
        while(ci < n && e[0] + e[1] != mx) {
            if(ci >= n-1) break;
            e = ask(++ci);
            c0 = e[0]; c1 = e[1];
        }
        if(ci >= n-1) break;
    }
    for(int i=0;i<n;i++) {
        if(vis[i]) continue;
        auto e = ask(i);
        if(e[0] + e[1] == 0) return i;
    }
    return 0;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:10:13: warning: variable 'c1' set but not used [-Wunused-but-set-variable]
   10 |     int c0, c1;
      |             ^~
prize.cpp:26:18: warning: 'c0' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |             else if(e[0] == c0) l = mid+1;
      |                  ^~
prize.cpp:23:21: warning: 'ci' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |             mid = (l+r) >> 1;
      |                   ~~^~~

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