Submission #301357

#	Time	Username	Problem	Language	Result	Execution time	Memory
301357		toloraia	The Big Prize (IOI17_prize)	C++14	20 / 100	139 ms	6892 KiB

prize

// 12:10
#include "prize.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
//#define ll __int128
#define ll long long
//#define int long long
#define LEFT(a) ((a)<<1)
#define RIGHT(a) (LEFT(a) + 1)
#define MID(a,b) ((a+b)>>1)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define y1 y122
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
/*
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")

#pragma GCC target("avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")

#pragma comment(linker, "/STACK: 20000000005")
*/

using namespace std;

const int N = 200005;

int a[N], b[N], F[N];

int Q;

void mak (int x){
    if (F[x])
        return;
    vector < int > res = ask (x);
    a[x] = res[0];
    b[x] = res[1];
    F[x] = 1;
    Q++;
    if (Q > 4500)
        assert (0);
}
int m;

vector < int > solve (int l, int r, int L, int R){
    vector < int > ans;
    if (l > r || L > R)
        return ans;
    int mid = l + r >> 1;
    while (mid >= l){
        mak (mid);
        if (a[mid] + b[mid] == m)
            break;
        ans.pb (mid);
        mid--;
    }
    int le = mid-1;
    int ri = (l+r>>1)+1;
    int LL = L-1;
    if (mid >= l)
        LL = a[mid];
    int RR = LL + 1 + (int)ans.size();
    vector < int > A = solve (l, le, L, LL);
    vector < int > B = solve (ri, r, RR, R);
    for (int x : A)
        ans.pb (x);
    for (int x : B)
        ans.pb (x);
    return ans;
}

int find_best(int n) {
    m = min (n-1, 446);
    vector < int > V;
    for (int i = 0; i < n; i++)
        V.pb (i);
    for (int i = 0; i < 20; i++)
        random_shuffle(V.begin(), V.end());
    int nn = 0;
    for (int i, x = 0; x <= m; x++){
        i = V[x];
        mak (i);
        nn = max (nn, a[i] + b[i]);
        if (nn > 26)
            break;
    }
    m = nn;
    vector < int > ans = solve (0, n-1, 1, m);
    for (int x : ans){
        mak (x);
        if (a[x] + b[x] == 0)
            return x;
    }
}

Compilation message (stderr)

prize.cpp:21:1: warning: "/*" within comment [-Wcomment]
   21 | /*
      |  
prize.cpp: In function 'std::vector<int> solve(int, int, int, int)':
prize.cpp:58:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |     int mid = l + r >> 1;
      |               ~~^~~
prize.cpp:67:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |     int ri = (l+r>>1)+1;
      |               ~^~
prize.cpp: In function 'int find_best(int)':
prize.cpp:83:20: warning: control reaches end of non-void function [-Wreturn-type]
   83 |     vector < int > V;
      |                    ^

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