oj.uz

Submission #766798

# Submission time Handle Problem Language Result Execution time Memory
766798 2023-06-26T07:33:51 Z danikoynov The Big Prize (IOI17_prize) C++14
20 / 100
 78 ms 1884 KB 
#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
map < int, vector < int > > mp;
map < int, int > used;
int cnt = 0;
vector < int > local_ask(int idx)
{
    if (used[idx])
        return mp[idx];
    cnt ++;
    //if (cnt == 1e4)
    //  while(true);
    used[idx] = 1;
    mp[idx] = ask(idx);
    return mp[idx];
}

const int maxn = 2e5 + 10;
vector < int > st;
int best;
void solve_range(int l, int r)
{
    ///cout << l << " " << r << endl;
    int m = (l + r) / 2;
    vector < int > lf = local_ask(l);
    vector < int > rf = local_ask(r);
    if (lf[1] == rf[1])
        return;
    while(m > l)
    {
        vector < int > mf = local_ask(m);
        if (mf[0] + mf[1] != best)
        {
            st.push_back(m);
            m --;
        }
        else
        {
            break;
        }
    }
    if (m == l)
    {
        m = (l + r) / 2 + 1;
        while(m < r)
        {
            vector < int > mf = local_ask(m);
            if (mf[0] + mf[1] != best)
                st.push_back(m), m ++;
            else
                break;
        }
    }
    if (m == r)
        return;

    vector < int > mf = ask(m);
    if (lf[0] != mf[0])
        solve_range(l, m);
    if (rf[0] != mf[0])
        solve_range(m, r);
}
int find_best(int n)
{
    vector < int > idc;
    for (int i = 0; i < n; i ++)
        idc.push_back(i);
    int nec = min(n, (int)sqrt(n) + 2);
    int mx = -1;
    for (int i = 0; i < nec; i ++)
    {
        vector < int > cur = local_ask(i);
        if (cur[0] + cur[1] > best)
        {
            best = cur[0] + cur[1];
            mx = i;
        }
    }
    int pt = n - 1;
    while(true)
    {
        vector < int > cur = local_ask(pt);
        if (cur[0] + cur[1] == best)
            break;
        pt --;
    }


    for (int i = 0; i < mx; i ++)
        st.push_back(i);
    for (int i = pt + 1; i < n; i ++)
        st.push_back(i);
    solve_range(mx, pt);

    for (int i = 0; i < st.size(); i ++)
    {
        vector < int > cur = ask(st[i]);
        if (cur[0] + cur[1] == 0)
            return st[i];
    }
    return -1;
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for (int i = 0; i < st.size(); i ++)
      |                     ~~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1564 KB Output is correct
2 Correct 4 ms 1432 KB Output is correct
3 Correct 3 ms 1432 KB Output is correct
4 Correct 5 ms 1352 KB Output is correct
5 Correct 4 ms 1352 KB Output is correct
6 Correct 4 ms 1440 KB Output is correct
7 Correct 4 ms 1352 KB Output is correct
8 Correct 3 ms 1436 KB Output is correct
9 Correct 4 ms 1352 KB Output is correct
10 Correct 3 ms 1352 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1432 KB Output is correct
2 Correct 5 ms 1352 KB Output is correct
3 Correct 5 ms 1352 KB Output is correct
4 Correct 3 ms 1436 KB Output is correct
5 Correct 5 ms 1436 KB Output is correct
6 Correct 5 ms 1436 KB Output is correct
7 Correct 6 ms 1432 KB Output is correct
8 Correct 5 ms 1352 KB Output is correct
9 Correct 3 ms 1432 KB Output is correct
10 Correct 4 ms 1352 KB Output is correct
11 Correct 14 ms 1352 KB Output is correct
12 Correct 10 ms 1352 KB Output is correct
13 Correct 6 ms 1432 KB Output is correct
14 Correct 18 ms 464 KB Output is correct
15 Partially correct 78 ms 1828 KB Partially correct - number of queries: 9201
16 Incorrect 58 ms 1884 KB Incorrect
17 Halted 0 ms 0 KB -