Submission #316174

#	Time	Username	Problem	Language	Result	Execution time	Memory
316174		nikatamliani	The Big Prize (IOI17_prize)	C++14	Compilation error	0 ms	0 KiB

prize

#include <bits/stdc++.h>
using namespace std;
#include "prize.h"
// int prize[] = {3, 1, 3, 2, 3, 3, 2, 3}; 
// int n = 8;
// int n;
// vector < int > prize;
// vector < int > ask(int x) {
//     int prefix = 0, suffix = 0; 
//     for(int i = 0; i < x; ++i) {
//         if(prize[i] < prize[x]) ++prefix;
//     }
//     for(int i = x + 1; i < n; ++i) {
//         if(prize[i] < prize[x]) ++suffix;
//     }
//     return {prefix, suffix};
// }
int find_best(int n) {
    int next = -1, at_most = 471;
    if(n > 10000) {
        vector < int > bad;
        for(int i = 0; i <= at_most; ++i) {
            bad = max(bad, ask(i));
        }
        for(int i = 0; i < n; i = next) {
            int l = i, r = n - 1; next = -1;
            vector < int > t = ask(i);
            if(t != bad) {
                next = i + 1;
                if(t[0] == 0 && t[1] == 0) return i; 
                continue;
            } 
            while(r >= l) {
                int m = l + r >> 1;
                vector < int > x = ask(m);
                if(x == t) {
                    next = m;
                    l = m + 1;
                } else {
                    r = m - 1; 
                }
            }
            assert(next >= 0);
            vector < int > tt = ask(next);
            for(int j = next + 1; j < n; ++j) {
                vector < int > p = ask(j);
                if(p[0] == 0 && p[1] == 0) return j; 
                if(p[0] > t[0] && t[1] == p[1] + j - next - 1) {
                    next = j;
                    break;
                }
            }
        }
        return -1;
    }
    //this is bad
    for(int i = 0; i < n; ++i) {
        vector < int > p = ask(i);
        if(!p[0] && !p[1]) return i; 
    }
}
// int find_answer(vector < int > x) {
//     for(int i = 0; i < x.size(); ++i) if(x[i] == 1) return i; 
// }
// int main() {
//     n = 8;
//     prize = {1, 2, 2, 3, 3, 3, 3, 3};
//     cout << find_best(n) << '\n';
//     cout << find_answer(prize) << '\n';
//     mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//     int op = 30000;
//     while(op--) {
//         n = 2e3;
//         int cnt_0 = 1;
//         int cnt_1 = 2;
//         int cnt_2 = 5;
//         int cnt_3 = n - 8; 
//         prize.resize(n);
//         for(int i = 0; i < cnt_0; ++i) {
//             prize[i] = 1;
//         }
//         for(int i = cnt_0; i < cnt_0 + cnt_1; ++i) {
//             prize[i] = 2;
//         }
//         for(int i = cnt_0 + cnt_1; i < cnt_0 + cnt_1 + cnt_2; ++i) {
//             prize[i] = 3;
//         }
//         for(int i = cnt_0 + cnt_1 + cnt_2; i < cnt_0 + cnt_1 + cnt_2 + cnt_3; ++i) {
//             prize[i] = 4;
//         }
//         for(int i = cnt_0 + cnt_1 + cnt_2 + cnt_3; i < n; ++i) {
//             prize[i] = 5;
//         }
//         shuffle(prize.begin(), prize.end(), rng);
//         // for(int i = 0; i < n; ++i) cout << prize[i] << ' ';
//         int answer = -1;
//         for(int i = 0; i < n; ++i) if(prize[i] == 1) answer = i;
//         // cout << find_best(n) << ' ' << answer << '\n';
//         if(find_best(n) == answer) {
//             // cout << "OK";
//         } else {
//             cout << "\nWRONG\n" << n << '\n';
//             for(int i : prize) cout << i << ' '; 
//         }
//     }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:34:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |                 int m = l + r >> 1;
      |                         ~~^~~
prize.cpp: At global scope:
prize.cpp:106:1: error: expected declaration before '}' token
  106 | }
      | ^
prize.cpp: In function 'int find_best(int)':
prize.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
   61 | }
      | ^