oj.uz

Submission #41867

# Submission time Handle Problem Language Result Execution time Memory
41867 2018-02-21T16:47:42 Z rahasia The Big Prize (IOI17_prize) C++14
20 / 100
 22 ms 2020 KB 
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

#define repU(x, y) for(int i = x; i <= y; ++i)
#define mp make_pair
#define pb push_back
#define allV(x) x.begin(), x.end()
#define fi first
#define se second

typedef long long LL;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int, int > pii;
typedef vector< pii > vpii;
typedef vector< LL > vL;
typedef vector< vL > vvL;
typedef vector< bool > vb;

// GLOBAL
int SUM = -1, bigN;
// --

int foo(int le, int ri, int BL, int BR) {
    if (le < 0 || ri >= bigN) return -1;
    if (le == ri) {
        vi tmp = ask(le);
        if (tmp[0] == 0 && tmp[1] == 0)
            return le;
        return -1;
    }

    int mid1 = (le + ri) / 2, mid2 = mid1+1, allL = 0, allR = 0;

    vi tmp = ask(mid1);
    allL = tmp[0] - BL;
    while (tmp[0] + tmp[1] != SUM && le <= mid1) {
        if (tmp[0] == 0 && tmp[1] == 0)
            return mid1;

        if (le > mid1-1) break;
        --mid1;
        tmp = ask(mid1);
        allL = tmp[0] - BL;
    }

    if (mid2 <= ri) {
        tmp = ask(mid2);
        allR = tmp[1] - BR;
    }

    while (tmp[0] + tmp[1] != SUM && mid2 <= ri) {
        if (tmp[0] == 0 && tmp[1] == 0)
            return mid2;

        if (mid2 + 1 > ri) break;
        ++mid2;
        tmp = ask(mid2);
        allR = tmp[1] - BR;
    }

    int res = -1;
    if (le <= mid1-1 && allL > 0) {
        tmp = ask(mid1-1);
        res = foo(le, mid1-1, BL, tmp[1]);
        if (res != -1) return res;
    }

    if (mid2+1 <= ri && allR > 0) {
        tmp = ask(mid2+1);
        res = foo(mid2+1, ri, tmp[0], BR);
        if (res != -1) return res;
    }

    return res;
}

int find_best(int n) {
    bigN = n;

    if (n <= 5000) {
        vi tmp;
        repU(0, n-1) {
            tmp = ask(i);
            if (tmp[0] == 0 && tmp[1] == 0)
                return i;
        }
        return -1;
    }
    else {
        vi tmp;
        repU(0,  450) {
            tmp = ask(i);
            if (tmp[0] == 0 && tmp[1] == 0)
                return i;

            SUM = max(SUM, tmp[0] + tmp[1]);
        }

        return foo(451, n-1, 0, 0);
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2020 KB Output is correct
2 Correct 3 ms 2020 KB Output is correct
3 Correct 0 ms 2020 KB Output is correct
4 Correct 4 ms 2020 KB Output is correct
5 Correct 4 ms 2020 KB Output is correct
6 Correct 0 ms 2020 KB Output is correct
7 Correct 2 ms 2020 KB Output is correct
8 Correct 1 ms 2020 KB Output is correct
9 Correct 6 ms 2020 KB Output is correct
10 Correct 10 ms 2020 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2020 KB Output is correct
2 Correct 0 ms 2020 KB Output is correct
3 Correct 1 ms 2020 KB Output is correct
4 Correct 2 ms 2020 KB Output is correct
5 Correct 2 ms 2020 KB Output is correct
6 Correct 0 ms 2020 KB Output is correct
7 Correct 6 ms 2020 KB Output is correct
8 Correct 0 ms 2020 KB Output is correct
9 Correct 3 ms 2020 KB Output is correct
10 Correct 0 ms 2020 KB Output is correct
11 Correct 5 ms 2020 KB Output is correct
12 Correct 2 ms 2020 KB Output is correct
13 Correct 0 ms 2020 KB Output is correct
14 Correct 7 ms 2020 KB Output is correct
15 Correct 6 ms 2020 KB Output is correct
16 Partially correct 22 ms 2020 KB Partially correct - number of queries: 9708
17 Correct 5 ms 2020 KB Output is correct
18 Incorrect 17 ms 2020 KB Incorrect
19 Halted 0 ms 0 KB -