Submission #619983

#	Time	Username	Problem	Language	Result	Execution time	Memory
619983		Ozy	The Big Prize (IOI17_prize)	C++17	100 / 100	48 ms	2060 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define lli int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define ini first
#define fin second
#define MAX 200000

lli mitad,cont,g;
queue<pair<lli,lli> > cola;
pair<lli,lli> act;
map<lli,lli> existe,id;
set<lli> pos[10];
set<lli>::iterator l,r;

lli premios[MAX+2][2];
bool nosepuede;
vector<int> a;

int find_best(int n) {

    cont = 0;
    cola.push({0,n-1});
    premios[n][0] = n+1;

    while (!cola.empty()) {

        act = cola.front();
        cola.pop();

        if (act.ini > act.fin) continue;
        mitad = (act.ini + act.fin)/2;

        //si puede haber algo dentro de mi
        nosepuede=false;
        rep(i,0,cont-1) {
            l = pos[i].lower_bound(mitad);
            r = l;
            l--;

            if ((*l) == -1) {
                if (premios[*r][0] == 0) {nosepuede=true; break;}
            }
            else if (premios[*l][1] == premios[*r][1] || premios[*l][1] == premios[*r][1]) {nosepuede=true; break;}
        }
        if (nosepuede) continue;

        a = ask(mitad);
        g = a[0]+a[1];
        if (g == 0) return mitad;

        existe[g]++;
        if (existe[g] == 1) {
            id[g] = cont;
            pos[cont].insert(-1);
            pos[cont].insert(n);
            cont++;
        }
        pos[id[g]].insert(mitad);
        premios[mitad][0] = a[0];
        premios[mitad][1] = a[1];

        cola.push({act.ini,mitad-1});
        cola.push({mitad+1,act.fin});
    }

}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
   72 | }
      | ^

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