Submission #289633

#	Time	Username	Problem	Language	Result	Execution time	Memory
289633		peti1234	The Big Prize (IOI17_prize)	C++17	0 / 100	9 ms	2816 KiB

prize

#include <bits/stdc++.h>
#include "prize.h";
using namespace std;
const int c=200002;
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) {
    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;
    }
    v[0]=1, v[n+1]=1;
    int r=n/500;
    for (int i=1; i<=500; i++) kerd(i*r);
    for (int i=1; i<=500; i+=r) if (bal[i]+jobb[i]==maxi) solve(el, i), el=i;
    solve(el, n+1);
    jobb[0]=maxi, bal[n+1]=maxi;
    return valasz;
}

Compilation message (stderr)

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

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