oj.uz

Submission #112246

# Submission time Handle Problem Language Result Execution time Memory
112246 2019-05-18T06:57:50 Z someone_aa The Big Prize (IOI17_prize) C++17
0 / 100
 7 ms 384 KB 
#include "prize.h"
#include <bits/stdc++.h>
#define P pair<int,int>
using namespace std;
const int maxn = 200100;
bool visited[maxn];
int q[maxn][2];
int max_sum, ind;
P query(int i) {
    if(visited[i]) return {q[i][0], q[i][1]};
    visited[i] = true;
    vector<int>curr = ask(i);
    q[i][0] = curr[0];
    q[i][1] = curr[1];
    return {q[i][0], q[i][1]};
}

int sum(int i) {
    query(i);
    return q[i][0] + q[i][1];
}

void solve(int l, int r) {
    if(l > r || ind != -1) return;

    P ql = query(l);
    P qr = query(r);

    if(ql.first + ql.second == 0) {
        ind = l;
        return;
    }

    if(qr.first + qr.second == 0) {
        ind = r;
        return;
    }

    if(ql.first + ql.second != max_sum) {
        solve(l+1, r);
        return;
    }

    if(qr.first + qr.second != max_sum) {
        solve(l, r-1);
        return;
    }

    int between  = qr.first - ql.first;
    if(between == 0) return;

    int mid = (l + r) / 2;

    solve(l, mid);
    solve(mid+1, r);
}

int find_best(int n) {
    for(int i=0;i<500;i++) {
        if(sum(i) == 0) return i;
        max_sum = max(max_sum, sum(i));
    }

    solve(0, n-1);
    return ind;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 384 KB answer is not correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 256 KB answer is not correct
2 Halted 0 ms 0 KB -