oj.uz

Submission #766777

# Submission time Handle Problem Language Result Execution time Memory
766777 2023-06-26T07:18:20 Z danikoynov The Big Prize (IOI17_prize) C++14
20 / 100
 82 ms 3388 KB 
#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
map < int, vector < int > > mp;
map < int, int > used;
vector < int > local_ask(int idx)
{
    if (used[idx])
        return mp[idx];
    used[idx] = 1;
    mp[idx] = ask(idx);
    return mp[idx];
}
int subsolve(vector < int > st)
{
    /**for (int i = 0; i < st.size(); i ++)
        cout << st[i] << " ";
    cout << endl;*/
    if (st.size() < 5000)
    {
        ///cout << "size " << st.size() << endl;
        for (int i = 0; i < st.size(); i ++)
        {
            vector < int > cur = ask(st[i]);
            if (cur[0] + cur[1] == 0)
                return st[i];
        }
    }
    if (st.size() == 1)
        return st[0];

    int nec = min((int)(st.size()), (int)(sqrt(st.size()) + 2));
    int mx = -1, best = 0;
    for (int i = 0; i < nec; i ++)
    {
        vector < int > cur = local_ask(st[i]);
        if (cur[0] + cur[1] > best)
        {
            best = cur[0] + cur[1];
            mx = i;
        }
    }

    vector < int > level;
    for (int i = 0; i < mx; i ++)
        level.push_back(st[i]);

    int t = mx, found = 0;
    ///cout << "here " << mx << endl;
    vector < int > base = local_ask(mx);
    while(t < st.size())
    {
        int l = t + 1, r = st.size() - 1;
        ///cout << t << endl;
        while(l <= r)
        {
            int m = (l + r) / 2;
            vector < int > cur = local_ask(st[m]);
            if (cur[0] + cur[1] != best)
                r = m - 1;
            else
            {
                int bet = cur[0] - base[0] - found;
                if (bet != 0)
                    r = m - 1;
                else
                    l = m + 1;
            }
        }
        if (l == st.size())
            break;
        t = l;
        found ++;
        level.push_back(st[t]);
    }
    return subsolve(level);
}
int find_best(int n) {
    vector < int > idc;
    for (int i = 0; i < n; i ++)
        idc.push_back(i);
    int ans = subsolve(idc);
	return ans;
}

Compilation message

prize.cpp: In function 'int subsolve(std::vector<int>)':
prize.cpp:22:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for (int i = 0; i < st.size(); i ++)
      |                         ~~^~~~~~~~~~~
prize.cpp:51:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     while(t < st.size())
      |           ~~^~~~~~~~~~~
prize.cpp:70:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         if (l == st.size())
      |             ~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1940 KB Output is correct
2 Correct 3 ms 1940 KB Output is correct
3 Correct 4 ms 1988 KB Output is correct
4 Correct 5 ms 1944 KB Output is correct
5 Correct 3 ms 1988 KB Output is correct
6 Correct 6 ms 1940 KB Output is correct
7 Correct 3 ms 1936 KB Output is correct
8 Correct 5 ms 1988 KB Output is correct
9 Correct 5 ms 1988 KB Output is correct
10 Correct 5 ms 1988 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1944 KB Output is correct
2 Correct 5 ms 1988 KB Output is correct
3 Correct 5 ms 1988 KB Output is correct
4 Correct 4 ms 1988 KB Output is correct
5 Correct 3 ms 1988 KB Output is correct
6 Correct 3 ms 1940 KB Output is correct
7 Correct 3 ms 1944 KB Output is correct
8 Correct 4 ms 1988 KB Output is correct
9 Correct 5 ms 1988 KB Output is correct
10 Correct 4 ms 1988 KB Output is correct
11 Correct 5 ms 2008 KB Output is correct
12 Correct 5 ms 2012 KB Output is correct
13 Correct 10 ms 1944 KB Output is correct
14 Correct 18 ms 712 KB Output is correct
15 Partially correct 77 ms 2972 KB Partially correct - number of queries: 7726
16 Partially correct 69 ms 3056 KB Partially correct - number of queries: 8454
17 Partially correct 42 ms 3132 KB Partially correct - number of queries: 8075
18 Partially correct 43 ms 3088 KB Partially correct - number of queries: 8537
19 Partially correct 39 ms 2964 KB Partially correct - number of queries: 7589
20 Partially correct 33 ms 1784 KB Partially correct - number of queries: 5331
21 Partially correct 56 ms 3004 KB Partially correct - number of queries: 8127
22 Partially correct 56 ms 2760 KB Partially correct - number of queries: 6105
23 Correct 9 ms 1948 KB Output is correct
24 Correct 8 ms 1996 KB Output is correct
25 Partially correct 43 ms 3048 KB Partially correct - number of queries: 8257
26 Partially correct 74 ms 3100 KB Partially correct - number of queries: 8251
27 Correct 6 ms 1932 KB Output is correct
28 Partially correct 47 ms 3076 KB Partially correct - number of queries: 8350
29 Partially correct 47 ms 2844 KB Partially correct - number of queries: 6861
30 Partially correct 76 ms 3060 KB Partially correct - number of queries: 8467
31 Partially correct 34 ms 3060 KB Partially correct - number of queries: 7998
32 Correct 12 ms 2000 KB Output is correct
33 Correct 0 ms 208 KB Output is correct
34 Partially correct 82 ms 3080 KB Partially correct - number of queries: 8183
35 Correct 5 ms 1944 KB Output is correct
36 Partially correct 61 ms 3092 KB Partially correct - number of queries: 8082
37 Correct 7 ms 1900 KB Output is correct
38 Correct 7 ms 1944 KB Output is correct
39 Partially correct 43 ms 3064 KB Partially correct - number of queries: 8204
40 Partially correct 65 ms 2884 KB Partially correct - number of queries: 7316
41 Partially correct 62 ms 3084 KB Partially correct - number of queries: 8213
42 Partially correct 51 ms 3000 KB Partially correct - number of queries: 8213
43 Partially correct 62 ms 3004 KB Partially correct - number of queries: 7803
44 Partially correct 52 ms 3124 KB Partially correct - number of queries: 8243
45 Partially correct 65 ms 3080 KB Partially correct - number of queries: 8164
46 Partially correct 55 ms 3060 KB Partially correct - number of queries: 8066
47 Partially correct 72 ms 3100 KB Partially correct - number of queries: 8288
48 Partially correct 77 ms 3036 KB Partially correct - number of queries: 8400
49 Partially correct 79 ms 3012 KB Partially correct - number of queries: 8068
50 Partially correct 45 ms 3052 KB Partially correct - number of queries: 8534
51 Partially correct 47 ms 3104 KB Partially correct - number of queries: 8222
52 Partially correct 48 ms 3052 KB Partially correct - number of queries: 8063
53 Correct 6 ms 1944 KB Output is correct
54 Partially correct 36 ms 3060 KB Partially correct - number of queries: 8193
55 Partially correct 78 ms 3024 KB Partially correct - number of queries: 8063
56 Partially correct 48 ms 3100 KB Partially correct - number of queries: 8533
57 Partially correct 57 ms 3068 KB Partially correct - number of queries: 8308
58 Partially correct 76 ms 3048 KB Partially correct - number of queries: 8355
59 Partially correct 65 ms 3076 KB Partially correct - number of queries: 8199
60 Partially correct 55 ms 2940 KB Partially correct - number of queries: 7796
61 Correct 7 ms 1988 KB Output is correct
62 Correct 4 ms 1944 KB Output is correct
63 Correct 6 ms 1944 KB Output is correct
64 Correct 9 ms 1944 KB Output is correct
65 Correct 6 ms 1944 KB Output is correct
66 Correct 10 ms 1944 KB Output is correct
67 Correct 9 ms 1940 KB Output is correct
68 Correct 9 ms 1980 KB Output is correct
69 Correct 7 ms 2016 KB Output is correct
70 Correct 5 ms 1948 KB Output is correct
71 Partially correct 55 ms 3156 KB Partially correct - number of queries: 8695
72 Correct 10 ms 2008 KB Output is correct
73 Partially correct 53 ms 3112 KB Partially correct - number of queries: 8563
74 Partially correct 56 ms 3116 KB Partially correct - number of queries: 8636
75 Correct 6 ms 1988 KB Output is correct
76 Partially correct 47 ms 2924 KB Partially correct - number of queries: 7457
77 Partially correct 61 ms 3076 KB Partially correct - number of queries: 8562
78 Correct 9 ms 2016 KB Output is correct
79 Correct 23 ms 2396 KB Output is correct
80 Partially correct 54 ms 3068 KB Partially correct - number of queries: 8550
81 Partially correct 54 ms 3308 KB Partially correct - number of queries: 8559
82 Partially correct 78 ms 3128 KB Partially correct - number of queries: 8490
83 Correct 5 ms 1988 KB Output is correct
84 Partially correct 77 ms 2856 KB Partially correct - number of queries: 7048
85 Partially correct 56 ms 3128 KB Partially correct - number of queries: 8538
86 Incorrect 71 ms 3388 KB Incorrect
87 Halted 0 ms 0 KB -