Submission #289637

#	Time	Username	Problem	Language	Result	Execution time	Memory
289637		peti1234	The Big Prize (IOI17_prize)	C++17	100 / 100	51 ms	2980 KiB

prize

#include <bits/stdc++.h>
#include "prize.h";
using namespace std;
const int c=200005;
int ert[c], bal[c], jobb[c], maxi, valasz, el, p;
bool v[c];
void kerd(int a) {
    if (v[a]) return;
    v[a]=1;
    vector<int> sz=ask(a-1);
    bal[a]=sz[0], jobb[a]=sz[1];
    p=bal[a]+jobb[a], ert[a]=p;
    if (!p) valasz=a-1;
    maxi=max(maxi, p);
}
void solve(int a, int b) {
    if (!v[a]) kerd(a);
    if (!v[b]) kerd(b);
    int db=jobb[a]-jobb[b];
    if (db) {
        int m=(a+b)/2, kis=m+1, nagy=m-1, p=0;
        while(p!=maxi && kis>a) {
            kis--, kerd(kis);
            p=ert[kis];
        }
        p=0;
        if (kis!=a) solve(a, kis);
        while(p!=maxi && nagy<b) {
            nagy++, kerd(nagy);
            p=ert[nagy];
        }
        if (nagy!=b) solve(nagy, b);
    }
}
int find_best(int n) {
    if (n<5000) {
        for (int i=1; i<=n; i++) kerd(i);
        return valasz;
    }
    int r=n/500;
    for (int i=1; i<=500; i++) kerd(i*r);
    v[0]=1, v[n+1]=1;
    jobb[0]=maxi, bal[n+1]=maxi, ert[0]=maxi, ert[n+1]=maxi;
    for (int i=1; i<=500; i++) if (ert[i*r]==maxi) solve(el, i*r), el=i*r;
    solve(el, n+1);
    return valasz;
}

Compilation message (stderr)

prize.cpp:2:19: warning: extra tokens at end of #include directive
    2 | #include "prize.h";
      |                   ^

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