Submission #297065

#	Time	Username	Problem	Language	Result	Execution time	Memory
297065		Trickster	The Big Prize (IOI17_prize)	C++14	97.51 / 100	66 ms	2048 KiB

prize

#include "prize.h"
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;

#define N 200010
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mod 1000000007
#define pii pair <int, int>
#define sz(a) int(a.size())
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
ll bigmod(ll a,ll e) {if(e==0)return 1;ll x=bigmod(a*a%mod,e>>1);return e&1?x*a%mod:x;}

pii p[N];
queue <pii> Q;

int find_best(int n)
{
    for(int i = 0; i < n; i++) p[i] = {-1, -1};

    Q.push({0, n-1});

    while(!Q.empty()) {
        int l = Q.front().ff, r = Q.front().ss;
        Q.pop();

        if(p[l].ff == -1 && p[l].ss == -1) {
            vector <int> cur = ask(l);
            p[l] = {cur[0], cur[1]};
        }
        if(p[r].ff == -1 && p[r].ss == -1) {
            vector <int> cur = ask(r);
            p[r] = {cur[0], cur[1]};
        }

        if(p[l].ff == 0 && p[l].ss == 0) return l;
        if(p[r].ff == 0 && p[r].ss == 0) return r;

        if(p[l].ss == p[r].ss || p[r].ff == p[l].ff) continue;            

        int md = (l+r)/2;

        Q.push({l, md});
        Q.push({md, r});
    }
}

Compilation message (stderr)

prize.cpp:23: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   23 | #pragma GCC optimization ("O3")
      | 
prize.cpp:24: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   24 | #pragma GCC optimization ("unroll-loops")
      | 
prize.cpp: In function 'int find_best(int)':
prize.cpp:59:1: warning: control reaches end of non-void function [-Wreturn-type]
   59 | }
      | ^

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