Submission #790797

#	Time	Username	Problem	Language	Result	Execution time	Memory
790797		peteza	The Big Prize (IOI17_prize)	C++14	0 / 100	4 ms	432 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 cl = ci, l, r, mid;
    while(1) {
        l = ci; r = n-1;
        int n0, n1;
        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;
        }
        //if(ci != 2)
        //cout << ci << ' ' << l << '\n';
        for(int i=ci;i<l;i++) 
            vis[i] = 1;
        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:22:13: warning: unused variable 'n0' [-Wunused-variable]
   22 |         int n0, n1;
      |             ^~
prize.cpp:22:17: warning: unused variable 'n1' [-Wunused-variable]
   22 |         int n0, n1;
      |                 ^~
prize.cpp:10:13: warning: variable 'c1' set but not used [-Wunused-but-set-variable]
   10 |     int c0, c1;
      |             ^~
prize.cpp:19:9: warning: unused variable 'cl' [-Wunused-variable]
   19 |     int cl = ci, l, r, mid;
      |         ^~
prize.cpp:27:18: warning: 'c0' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |             else if(e[0] == c0) l = mid+1;
      |                  ^~
prize.cpp:40:9: warning: 'ci' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |         if(ci >= n-1) break;
      |         ^~

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