oj.uz

Submission #766803

# Submission time Handle Problem Language Result Execution time Memory
766803 2023-06-26T07:38:43 Z danikoynov The Big Prize (IOI17_prize) C++14
20 / 100
 87 ms 2520 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 << " " << cnt << 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 = local_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);

    //cout << st.size() << " " << cnt << endl;
    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:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i = 0; i < st.size(); i ++)
      |                     ~~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1352 KB Output is correct
2 Correct 4 ms 1436 KB Output is correct
3 Correct 3 ms 1352 KB Output is correct
4 Correct 3 ms 1352 KB Output is correct
5 Correct 5 ms 1352 KB Output is correct
6 Correct 3 ms 1432 KB Output is correct
7 Correct 3 ms 1440 KB Output is correct
8 Correct 4 ms 1412 KB Output is correct
9 Correct 4 ms 1352 KB Output is correct
10 Correct 5 ms 1352 KB Output is correct
11 Correct 10 ms 1352 KB Output is correct
12 Correct 9 ms 1432 KB Output is correct
13 Correct 7 ms 1436 KB Output is correct
14 Correct 12 ms 600 KB Output is correct
15 Partially correct 22 ms 1844 KB Partially correct - number of queries: 5107
16 Partially correct 25 ms 1896 KB Partially correct - number of queries: 5897
17 Partially correct 43 ms 1804 KB Partially correct - number of queries: 5209
18 Partially correct 35 ms 1856 KB Partially correct - number of queries: 6059
19 Correct 40 ms 1960 KB Output is correct
20 Correct 20 ms 1104 KB Output is correct
21 Partially correct 32 ms 1864 KB Partially correct - number of queries: 5477
22 Correct 21 ms 1624 KB Output is correct
23 Correct 3 ms 1480 KB Output is correct
24 Correct 8 ms 1352 KB Output is correct
25 Partially correct 24 ms 1860 KB Partially correct - number of queries: 5320
26 Partially correct 39 ms 1724 KB Partially correct - number of queries: 5273
27 Correct 5 ms 1428 KB Output is correct
28 Partially correct 38 ms 1724 KB Partially correct - number of queries: 5583
29 Correct 29 ms 1612 KB Output is correct
30 Partially correct 39 ms 1776 KB Partially correct - number of queries: 6018
31 Partially correct 38 ms 1852 KB Partially correct - number of queries: 5174
32 Correct 9 ms 1352 KB Output is correct
33 Correct 1 ms 208 KB Output is correct
34 Partially correct 48 ms 1808 KB Partially correct - number of queries: 5463
35 Correct 6 ms 1428 KB Output is correct
36 Partially correct 26 ms 1800 KB Partially correct - number of queries: 5371
37 Correct 7 ms 1352 KB Output is correct
38 Correct 3 ms 1428 KB Output is correct
39 Partially correct 24 ms 1844 KB Partially correct - number of queries: 5548
40 Partially correct 40 ms 1700 KB Partially correct - number of queries: 5307
41 Partially correct 32 ms 1852 KB Partially correct - number of queries: 5691
42 Partially correct 41 ms 1868 KB Partially correct - number of queries: 5691
43 Partially correct 24 ms 1908 KB Partially correct - number of queries: 5521
44 Partially correct 44 ms 1816 KB Partially correct - number of queries: 5543
45 Partially correct 46 ms 1820 KB Partially correct - number of queries: 5086
46 Partially correct 50 ms 1864 KB Partially correct - number of queries: 5208
47 Partially correct 23 ms 1812 KB Partially correct - number of queries: 5239
48 Partially correct 34 ms 1856 KB Partially correct - number of queries: 5813
49 Partially correct 51 ms 1804 KB Partially correct - number of queries: 5262
50 Partially correct 57 ms 1848 KB Partially correct - number of queries: 6065
51 Partially correct 49 ms 1852 KB Partially correct - number of queries: 5553
52 Partially correct 49 ms 1852 KB Partially correct - number of queries: 5213
53 Correct 6 ms 1436 KB Output is correct
54 Partially correct 48 ms 1844 KB Partially correct - number of queries: 5522
55 Partially correct 35 ms 1852 KB Partially correct - number of queries: 5207
56 Partially correct 37 ms 1852 KB Partially correct - number of queries: 6049
57 Partially correct 40 ms 1784 KB Partially correct - number of queries: 5785
58 Partially correct 31 ms 1932 KB Partially correct - number of queries: 5801
59 Partially correct 35 ms 1804 KB Partially correct - number of queries: 5694
60 Partially correct 24 ms 1840 KB Partially correct - number of queries: 5623
61 Correct 4 ms 1432 KB Output is correct
62 Correct 3 ms 1432 KB Output is correct
63 Correct 3 ms 1432 KB Output is correct
64 Correct 4 ms 1436 KB Output is correct
65 Correct 5 ms 1352 KB Output is correct
66 Correct 10 ms 1428 KB Output is correct
67 Correct 7 ms 1424 KB Output is correct
68 Correct 4 ms 1436 KB Output is correct
69 Correct 6 ms 1436 KB Output is correct
70 Correct 4 ms 1432 KB Output is correct
71 Partially correct 52 ms 1988 KB Partially correct - number of queries: 5680
72 Correct 7 ms 1352 KB Output is correct
73 Partially correct 38 ms 1800 KB Partially correct - number of queries: 5610
74 Partially correct 27 ms 1900 KB Partially correct - number of queries: 5640
75 Correct 4 ms 1352 KB Output is correct
76 Correct 35 ms 1696 KB Output is correct
77 Partially correct 27 ms 1852 KB Partially correct - number of queries: 6230
78 Correct 7 ms 1352 KB Output is correct
79 Correct 26 ms 1472 KB Output is correct
80 Partially correct 45 ms 1812 KB Partially correct - number of queries: 6200
81 Partially correct 56 ms 1848 KB Partially correct - number of queries: 6206
82 Partially correct 50 ms 1892 KB Partially correct - number of queries: 6155
83 Correct 11 ms 1352 KB Output is correct
84 Partially correct 22 ms 1752 KB Partially correct - number of queries: 5160
85 Partially correct 55 ms 1900 KB Partially correct - number of queries: 6155
86 Incorrect 87 ms 2520 KB Incorrect
87 Halted 0 ms 0 KB -