Submission #311204

#	Time	Username	Problem	Language	Result	Execution time	Memory
311204		aZvezda	The Big Prize (IOI17_prize)	C++14	96.41 / 100	73 ms	968 KiB

prize

//#include "prize.h"
#include <vector>

int find_best(int n);
std::vector<int> ask(int i);

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "

map<int, vector<int> > prec;

vector<int> query(int x) {
    if(prec.find(x) != prec.end()) {
        return prec[x];
    } else {
        return prec[x] = ask(x);
    }
}

set<int> st;

bool eval(vector<int> curr, int ind, int bigSum) {
    auto nxt = query(ind);
    if(nxt[0] + nxt[1] != bigSum) {
        st.insert(ind);
        return true;
    } else if(nxt[0] != curr[0]) {
        return true;
    } else {
        return false;
    }
}

int find_best(int n) {
    prec.clear();
    int sqr = sqrt(n), group;

    int bigSum = 0;
    for(int i = n - 1; i > 0; i -= sqr) {
        auto now = query(i);
        chkmax(bigSum, now[0] + now[1]);
        group = i;
        //cout << i << " " << now[0] << " " << now[1] << endl;
    }
    for(int i = 0; i < n;) {
        if(i > group) {group += sqr;}
        while(!st.empty() && *st.begin() < i) {
            auto now = query(*st.begin());
            if(now[0] + now[1] == 0) {
                return *st.begin();
            }
            st.erase(st.begin());
        }
        //cout << i << endl;
        auto now = query(i);
        if(now[0] + now[1] != bigSum) {
            if(now[0] + now[1] == 0) {
                return i;
            }
            i ++;
            continue;
        }
        if(!eval(now, group, bigSum)) {
            i = group + 1;
            continue;
        }
        int l = i, r = group;
        if(!st.empty()) {
            r = min(group, *st.begin());
        }
        while(l < r - 1) {
            int m = (l + r) / 2ll;
            if(eval(now, m, bigSum)) {
                r = m;
            } else {
                l = m;
            }
        }
        i = r; continue;
    }
    for(auto it : prec) {
        if(it.second[0] + it.second[1] == 0) {
            return it.first;
        }
    }
    return -1;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:56:30: warning: 'group' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |         if(i > group) {group += sqr;}
      |                        ~~~~~~^~~~~~

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