oj.uz

Submission #766774

# Submission time Handle Problem Language Result Execution time Memory
766774 2023-06-26T07:14:11 Z danikoynov The Big Prize (IOI17_prize) C++14
20 / 100
 77 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() == 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:41:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     while(t < st.size())
      |           ~~^~~~~~~~~~~
prize.cpp:60:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         if (l == st.size())
      |             ~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1944 KB Output is correct
2 Correct 3 ms 1952 KB Output is correct
3 Correct 6 ms 1988 KB Output is correct
4 Correct 6 ms 1988 KB Output is correct
5 Correct 5 ms 1988 KB Output is correct
6 Correct 4 ms 1948 KB Output is correct
7 Correct 6 ms 1948 KB Output is correct
8 Correct 5 ms 1988 KB Output is correct
9 Correct 3 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 4 ms 1940 KB Output is correct
2 Correct 5 ms 1940 KB Output is correct
3 Correct 5 ms 1944 KB Output is correct
4 Correct 3 ms 1948 KB Output is correct
5 Correct 6 ms 1940 KB Output is correct
6 Correct 3 ms 1924 KB Output is correct
7 Correct 5 ms 1988 KB Output is correct
8 Correct 5 ms 1944 KB Output is correct
9 Correct 6 ms 1988 KB Output is correct
10 Correct 4 ms 1988 KB Output is correct
11 Correct 10 ms 1988 KB Output is correct
12 Correct 5 ms 2016 KB Output is correct
13 Correct 10 ms 1940 KB Output is correct
14 Correct 16 ms 728 KB Output is correct
15 Partially correct 68 ms 2948 KB Partially correct - number of queries: 7660
16 Partially correct 63 ms 3296 KB Partially correct - number of queries: 8063
17 Partially correct 61 ms 3132 KB Partially correct - number of queries: 8074
18 Partially correct 44 ms 3044 KB Partially correct - number of queries: 8065
19 Partially correct 34 ms 2960 KB Partially correct - number of queries: 7588
20 Partially correct 37 ms 1940 KB Partially correct - number of queries: 5211
21 Partially correct 76 ms 3000 KB Partially correct - number of queries: 7955
22 Partially correct 32 ms 2788 KB Partially correct - number of queries: 6072
23 Correct 4 ms 1944 KB Output is correct
24 Correct 5 ms 2004 KB Output is correct
25 Partially correct 71 ms 3060 KB Partially correct - number of queries: 8002
26 Partially correct 34 ms 3076 KB Partially correct - number of queries: 7998
27 Correct 6 ms 1988 KB Output is correct
28 Partially correct 69 ms 3060 KB Partially correct - number of queries: 7904
29 Partially correct 46 ms 2872 KB Partially correct - number of queries: 6528
30 Partially correct 73 ms 3024 KB Partially correct - number of queries: 7999
31 Partially correct 65 ms 3004 KB Partially correct - number of queries: 7997
32 Correct 6 ms 1936 KB Output is correct
33 Correct 1 ms 208 KB Output is correct
34 Partially correct 77 ms 3072 KB Partially correct - number of queries: 8039
35 Correct 6 ms 1988 KB Output is correct
36 Partially correct 34 ms 3064 KB Partially correct - number of queries: 7978
37 Correct 6 ms 2016 KB Output is correct
38 Correct 6 ms 1944 KB Output is correct
39 Partially correct 75 ms 3092 KB Partially correct - number of queries: 7997
40 Partially correct 37 ms 2852 KB Partially correct - number of queries: 6916
41 Partially correct 56 ms 3012 KB Partially correct - number of queries: 7944
42 Partially correct 75 ms 3128 KB Partially correct - number of queries: 7944
43 Partially correct 61 ms 3048 KB Partially correct - number of queries: 7561
44 Partially correct 46 ms 3068 KB Partially correct - number of queries: 8060
45 Partially correct 69 ms 3032 KB Partially correct - number of queries: 8015
46 Partially correct 72 ms 3044 KB Partially correct - number of queries: 8065
47 Partially correct 43 ms 3056 KB Partially correct - number of queries: 8071
48 Partially correct 34 ms 3060 KB Partially correct - number of queries: 8064
49 Partially correct 72 ms 3256 KB Partially correct - number of queries: 8034
50 Partially correct 48 ms 3052 KB Partially correct - number of queries: 8062
51 Partially correct 58 ms 3076 KB Partially correct - number of queries: 8037
52 Partially correct 61 ms 3084 KB Partially correct - number of queries: 8059
53 Correct 4 ms 1988 KB Output is correct
54 Partially correct 76 ms 3048 KB Partially correct - number of queries: 8000
55 Partially correct 74 ms 3136 KB Partially correct - number of queries: 8062
56 Partially correct 53 ms 3236 KB Partially correct - number of queries: 8061
57 Partially correct 71 ms 3036 KB Partially correct - number of queries: 7977
58 Partially correct 55 ms 3044 KB Partially correct - number of queries: 8018
59 Partially correct 41 ms 3084 KB Partially correct - number of queries: 7930
60 Partially correct 51 ms 3004 KB Partially correct - number of queries: 7547
61 Correct 4 ms 1944 KB Output is correct
62 Correct 6 ms 1988 KB Output is correct
63 Correct 7 ms 1944 KB Output is correct
64 Correct 4 ms 1984 KB Output is correct
65 Correct 5 ms 1988 KB Output is correct
66 Correct 5 ms 2008 KB Output is correct
67 Correct 10 ms 2016 KB Output is correct
68 Correct 3 ms 1944 KB Output is correct
69 Correct 11 ms 1944 KB Output is correct
70 Correct 8 ms 1988 KB Output is correct
71 Partially correct 75 ms 3052 KB Partially correct - number of queries: 8223
72 Correct 10 ms 2012 KB Output is correct
73 Partially correct 46 ms 3068 KB Partially correct - number of queries: 8098
74 Partially correct 74 ms 3076 KB Partially correct - number of queries: 8168
75 Correct 3 ms 1988 KB Output is correct
76 Partially correct 48 ms 2876 KB Partially correct - number of queries: 7057
77 Partially correct 52 ms 3040 KB Partially correct - number of queries: 8090
78 Correct 10 ms 1988 KB Output is correct
79 Correct 18 ms 2388 KB Output is correct
80 Partially correct 45 ms 3124 KB Partially correct - number of queries: 8078
81 Partially correct 72 ms 3128 KB Partially correct - number of queries: 8087
82 Partially correct 73 ms 3040 KB Partially correct - number of queries: 8022
83 Correct 5 ms 1988 KB Output is correct
84 Partially correct 64 ms 2896 KB Partially correct - number of queries: 6664
85 Partially correct 74 ms 3132 KB Partially correct - number of queries: 8066
86 Incorrect 74 ms 3388 KB Incorrect
87 Halted 0 ms 0 KB -