oj.uz

답안 #766771

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
766771 2023-06-26T07:11:17 Z danikoynov 커다란 상품 (IOI17_prize) C++14
20 / 100
 75 ms 2036 KB 
#include "prize.h"
#include<bits/stdc++.h>
using namespace std;

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 = 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 = 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 = 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:32:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     while(t < st.size())
      |           ~~^~~~~~~~~~~
prize.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         if (l == st.size())
      |             ~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1988 KB Output is correct
2 Correct 5 ms 1988 KB Output is correct
3 Correct 6 ms 1940 KB Output is correct
4 Correct 5 ms 1988 KB Output is correct
5 Correct 4 ms 1944 KB Output is correct
6 Correct 5 ms 1988 KB Output is correct
7 Correct 3 ms 1940 KB Output is correct
8 Correct 3 ms 1940 KB Output is correct
9 Correct 4 ms 1988 KB Output is correct
10 Correct 5 ms 1988 KB Output is correct

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1988 KB Output is correct
2 Correct 6 ms 1944 KB Output is correct
3 Correct 3 ms 1988 KB Output is correct
4 Correct 3 ms 1944 KB Output is correct
5 Correct 5 ms 1988 KB Output is correct
6 Correct 3 ms 1944 KB Output is correct
7 Correct 3 ms 1988 KB Output is correct
8 Correct 3 ms 1988 KB Output is correct
9 Correct 5 ms 1988 KB Output is correct
10 Correct 5 ms 1988 KB Output is correct
11 Correct 5 ms 1936 KB Output is correct
12 Correct 11 ms 1944 KB Output is correct
13 Correct 11 ms 1940 KB Output is correct
14 Correct 16 ms 464 KB Output is correct
15 Partially correct 59 ms 1988 KB Partially correct - number of queries: 7764
16 Partially correct 32 ms 1944 KB Partially correct - number of queries: 8382
17 Partially correct 69 ms 1944 KB Partially correct - number of queries: 8488
18 Partially correct 28 ms 1932 KB Partially correct - number of queries: 8379
19 Partially correct 41 ms 1948 KB Partially correct - number of queries: 7923
20 Partially correct 37 ms 1176 KB Partially correct - number of queries: 5501
21 Partially correct 47 ms 1988 KB Partially correct - number of queries: 8275
22 Partially correct 37 ms 1940 KB Partially correct - number of queries: 6213
23 Correct 4 ms 1944 KB Output is correct
24 Correct 11 ms 1988 KB Output is correct
25 Partially correct 38 ms 1988 KB Partially correct - number of queries: 8408
26 Partially correct 39 ms 1944 KB Partially correct - number of queries: 8546
27 Correct 3 ms 1988 KB Output is correct
28 Partially correct 60 ms 1940 KB Partially correct - number of queries: 8243
29 Partially correct 23 ms 1988 KB Partially correct - number of queries: 6854
30 Partially correct 62 ms 1988 KB Partially correct - number of queries: 8256
31 Partially correct 28 ms 1944 KB Partially correct - number of queries: 8337
32 Correct 9 ms 1988 KB Output is correct
33 Correct 1 ms 208 KB Output is correct
34 Partially correct 54 ms 1988 KB Partially correct - number of queries: 8402
35 Correct 4 ms 1944 KB Output is correct
36 Partially correct 53 ms 1988 KB Partially correct - number of queries: 8338
37 Correct 11 ms 1988 KB Output is correct
38 Correct 4 ms 1944 KB Output is correct
39 Partially correct 52 ms 1988 KB Partially correct - number of queries: 8270
40 Partially correct 30 ms 1924 KB Partially correct - number of queries: 7064
41 Partially correct 28 ms 1944 KB Partially correct - number of queries: 8394
42 Partially correct 60 ms 1988 KB Partially correct - number of queries: 8394
43 Partially correct 49 ms 1944 KB Partially correct - number of queries: 8139
44 Partially correct 37 ms 1988 KB Partially correct - number of queries: 8402
45 Partially correct 44 ms 1944 KB Partially correct - number of queries: 8430
46 Partially correct 66 ms 1988 KB Partially correct - number of queries: 8498
47 Partially correct 52 ms 1936 KB Partially correct - number of queries: 8456
48 Partially correct 74 ms 1988 KB Partially correct - number of queries: 8389
49 Partially correct 29 ms 1944 KB Partially correct - number of queries: 8389
50 Partially correct 39 ms 1988 KB Partially correct - number of queries: 8376
51 Partially correct 71 ms 1988 KB Partially correct - number of queries: 8425
52 Partially correct 67 ms 1988 KB Partially correct - number of queries: 8400
53 Correct 3 ms 1948 KB Output is correct
54 Partially correct 70 ms 1940 KB Partially correct - number of queries: 8286
55 Partially correct 30 ms 1940 KB Partially correct - number of queries: 8490
56 Partially correct 68 ms 1944 KB Partially correct - number of queries: 8375
57 Partially correct 56 ms 1988 KB Partially correct - number of queries: 8343
58 Partially correct 65 ms 1988 KB Partially correct - number of queries: 8395
59 Partially correct 65 ms 1944 KB Partially correct - number of queries: 8395
60 Partially correct 61 ms 1988 KB Partially correct - number of queries: 8273
61 Correct 5 ms 1988 KB Output is correct
62 Correct 8 ms 1988 KB Output is correct
63 Correct 7 ms 1944 KB Output is correct
64 Correct 7 ms 1988 KB Output is correct
65 Correct 3 ms 1940 KB Output is correct
66 Correct 23 ms 1944 KB Output is correct
67 Correct 40 ms 1988 KB Output is correct
68 Correct 3 ms 1948 KB Output is correct
69 Correct 27 ms 2036 KB Output is correct
70 Correct 24 ms 1988 KB Output is correct
71 Partially correct 48 ms 1988 KB Partially correct - number of queries: 8388
72 Correct 10 ms 1988 KB Output is correct
73 Partially correct 45 ms 1988 KB Partially correct - number of queries: 8264
74 Partially correct 49 ms 1988 KB Partially correct - number of queries: 8307
75 Correct 5 ms 1988 KB Output is correct
76 Partially correct 55 ms 1988 KB Partially correct - number of queries: 7172
77 Partially correct 69 ms 1944 KB Partially correct - number of queries: 8399
78 Correct 9 ms 1948 KB Output is correct
79 Correct 36 ms 1988 KB Output is correct
80 Partially correct 75 ms 1988 KB Partially correct - number of queries: 8382
81 Partially correct 59 ms 1988 KB Partially correct - number of queries: 8387
82 Partially correct 29 ms 1908 KB Partially correct - number of queries: 8286
83 Correct 6 ms 1988 KB Output is correct
84 Partially correct 63 ms 1988 KB Partially correct - number of queries: 6902
85 Partially correct 63 ms 1988 KB Partially correct - number of queries: 8409
86 Incorrect 36 ms 1940 KB Incorrect
87 Halted 0 ms 0 KB -