oj.uz

Submission #965520

# Submission time Handle Problem Language Result Execution time Memory
965520 2024-04-18T18:53:35 Z IUA_Hasin The Big Prize (IOI17_prize) C++17
90 / 100
 58 ms 5168 KB 
#include "prize.h"

#include <bits/stdc++.h>
 
#define endl                                "\n"
#define yeap                                cout<<"YES"<<endl
#define nope                                cout<<"NO"<<endl
#define ll                                  long long
 
using namespace std;

const ll max_gems = 480;
bool gems[200005];
std::vector<pair<ll,ll>> response;



vector<int> askk(int i) {
    if(response[i] == make_pair(-1ll, -1ll)) {
        vector<int> res = ask(i);
        response[i] = make_pair(res[0], res[1]);
        return res;
    }

    vector<int> res;

    res.push_back(response[i].first);
    res.push_back(response[i].second);
	

	return res;
}


int find_best(int n) {
	ll mx = 0;
	ll mxind = 0;

    response.resize(n+5, {-1,-1});


  
	for(int i=1; i<=max_gems; i++){
		std::vector<int> v = askk(i-1);
		ll a = v[0];
		ll b = v[1];
		ll c = a+b;
		if(c==0){
			return i-1;
		}
		if(c >= mx){
			mx = c;
			mxind = i-1;
		}
	}


    for(int i=1; i<=max_gems; i++){
		std::vector<int> v = askk(i-1);
		ll a = v[0];
		ll b = v[1];
		ll c = a+b;
		if(c==0){
			return (i-1);
		}
		if(c != mx){
			gems[i-1] = true;
		}
	}

  ////////////////////////////////// Thik ache /////////////////////////////////


    

    int cur_lolipop = max_gems, left, right;

    while(true) {
		// cout << cur_lolipop << " " << 79 << endl;
        vector<int> v = askk(cur_lolipop);
		ll a = v[0];
		ll b = v[1];
		ll c = a+b;
		if(c==0){
			return cur_lolipop;
		}

		if(c != mx){
			gems[cur_lolipop] = true;
            cur_lolipop++;
		} else {
            left = a, right = b;
            break;
        }
    }



    while(right != 0) {

		// cout << l << " " << r << endl;

        int l = cur_lolipop+1, r = n-1;

		// cout << l << " " << r << endl;

        while(l < r) {

            int mid = (l+r)/2;
			// cout << mid << " " << 105 << endl;
            vector<int> v = askk(mid);

            ll a = v[0];
    		ll b = v[1];
    		ll c = a+b;

			// cout << c << endl;

			if(c==0){
				return mid;
			}

            if(c < left + right) {
                gems[mid] == true;
                r = mid;
            } else if(a == left) {
                l = mid+1;
                for(int i = l; i <= mid; i++) {
                    response[i] = {left, right};
                }
            } else {
                r = mid - 1;
            }

        }

		vector<int> v = askk(l);

            ll a = v[0];
    		ll b = v[1];
    		ll c = a+b;

			// cout << c << endl;

			if(c==0){
				return l;
			}


        gems[l] = true;
        cur_lolipop = l+1;


		// if(cur_lolipop==n){
		// 	return cur_lolipop;
		// }

        while(true) {
			// cout << cur_lolipop << " " << 134 << endl;
            vector<int> v = askk(cur_lolipop);
    		ll a = v[0];
    		ll b = v[1];
    		ll c = a+b;
			if(c==0){
				return cur_lolipop;
			}
    		if(c != mx){
    			gems[cur_lolipop] = true;
                cur_lolipop++;
    		} else {
                left = a, right = b;
                break;
            }
        }
      
    }



    
    

    





}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:124:27: warning: statement has no effect [-Wunused-value]
  124 |                 gems[mid] == true;
      |                 ~~~~~~~~~~^~~~~~~
prize.cpp:37:5: warning: variable 'mxind' set but not used [-Wunused-but-set-variable]
   37 |  ll mxind = 0;
      |     ^~~~~
prize.cpp:189:1: warning: control reaches end of non-void function [-Wreturn-type]
  189 | }
      | ^

Subtask #1
20.0 / 20.0

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

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3416 KB Output is correct
2 Correct 3 ms 3668 KB Output is correct
3 Correct 3 ms 3416 KB Output is correct
4 Correct 3 ms 3412 KB Output is correct
5 Correct 4 ms 3416 KB Output is correct
6 Correct 1 ms 3416 KB Output is correct
7 Correct 4 ms 3416 KB Output is correct
8 Correct 4 ms 3416 KB Output is correct
9 Correct 4 ms 3416 KB Output is correct
10 Correct 3 ms 3416 KB Output is correct
11 Correct 4 ms 3628 KB Output is correct
12 Correct 3 ms 3416 KB Output is correct
13 Correct 7 ms 3584 KB Output is correct
14 Correct 4 ms 792 KB Output is correct
15 Correct 10 ms 3608 KB Output is correct
16 Partially correct 45 ms 4712 KB Partially correct - number of queries: 7126
17 Correct 3 ms 3416 KB Output is correct
18 Partially correct 50 ms 4216 KB Partially correct - number of queries: 8258
19 Correct 3 ms 3416 KB Output is correct
20 Correct 12 ms 2024 KB Output is correct
21 Correct 18 ms 4384 KB Output is correct
22 Correct 5 ms 3844 KB Output is correct
23 Correct 3 ms 3672 KB Output is correct
24 Correct 3 ms 3416 KB Output is correct
25 Correct 21 ms 3848 KB Output is correct
26 Correct 27 ms 3844 KB Output is correct
27 Correct 5 ms 3592 KB Output is correct
28 Partially correct 36 ms 4252 KB Partially correct - number of queries: 7808
29 Partially correct 30 ms 4632 KB Partially correct - number of queries: 6029
30 Partially correct 41 ms 4952 KB Partially correct - number of queries: 8203
31 Correct 3 ms 3416 KB Output is correct
32 Correct 5 ms 3848 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 12 ms 4092 KB Output is correct
35 Correct 4 ms 3596 KB Output is correct
36 Correct 9 ms 3844 KB Output is correct
37 Correct 4 ms 3584 KB Output is correct
38 Correct 3 ms 3416 KB Output is correct
39 Correct 16 ms 5168 KB Output is correct
40 Partially correct 43 ms 4180 KB Partially correct - number of queries: 7110
41 Partially correct 31 ms 4168 KB Partially correct - number of queries: 5137
42 Partially correct 27 ms 4624 KB Partially correct - number of queries: 5137
43 Correct 19 ms 4660 KB Output is correct
44 Correct 28 ms 4348 KB Output is correct
45 Correct 22 ms 4268 KB Output is correct
46 Correct 3 ms 3416 KB Output is correct
47 Correct 16 ms 4396 KB Output is correct
48 Partially correct 38 ms 4152 KB Partially correct - number of queries: 6241
49 Correct 5 ms 3584 KB Output is correct
50 Partially correct 40 ms 4664 KB Partially correct - number of queries: 8255
51 Correct 19 ms 4384 KB Output is correct
52 Correct 3 ms 3416 KB Output is correct
53 Correct 3 ms 3848 KB Output is correct
54 Correct 16 ms 4148 KB Output is correct
55 Correct 3 ms 3416 KB Output is correct
56 Partially correct 49 ms 5148 KB Partially correct - number of queries: 8252
57 Partially correct 37 ms 4628 KB Partially correct - number of queries: 6158
58 Partially correct 27 ms 4156 KB Partially correct - number of queries: 6229
59 Partially correct 22 ms 4176 KB Partially correct - number of queries: 5132
60 Correct 24 ms 4632 KB Output is correct
61 Correct 5 ms 3588 KB Output is correct
62 Correct 3 ms 3416 KB Output is correct
63 Correct 4 ms 3844 KB Output is correct
64 Correct 3 ms 3588 KB Output is correct
65 Correct 3 ms 3416 KB Output is correct
66 Correct 6 ms 3504 KB Output is correct
67 Correct 4 ms 3628 KB Output is correct
68 Correct 3 ms 3416 KB Output is correct
69 Correct 5 ms 3416 KB Output is correct
70 Correct 3 ms 3416 KB Output is correct
71 Partially correct 52 ms 3920 KB Partially correct - number of queries: 8247
72 Correct 7 ms 3940 KB Output is correct
73 Partially correct 42 ms 4384 KB Partially correct - number of queries: 8140
74 Partially correct 44 ms 4124 KB Partially correct - number of queries: 8181
75 Correct 5 ms 3588 KB Output is correct
76 Partially correct 26 ms 3872 KB Partially correct - number of queries: 7098
77 Partially correct 58 ms 4420 KB Partially correct - number of queries: 8297
78 Correct 5 ms 4104 KB Output is correct
79 Correct 26 ms 4356 KB Output is correct
80 Partially correct 44 ms 4900 KB Partially correct - number of queries: 8310
81 Partially correct 46 ms 4920 KB Partially correct - number of queries: 8298
82 Partially correct 42 ms 4628 KB Partially correct - number of queries: 8194
83 Correct 3 ms 3588 KB Output is correct
84 Partially correct 27 ms 3852 KB Partially correct - number of queries: 6854
85 Partially correct 41 ms 4500 KB Partially correct - number of queries: 8230
86 Correct 3 ms 3416 KB Output is correct
87 Correct 3 ms 3416 KB Output is correct
88 Correct 3 ms 3416 KB Output is correct
89 Correct 3 ms 3416 KB Output is correct
90 Correct 3 ms 3416 KB Output is correct
91 Correct 3 ms 3416 KB Output is correct
92 Correct 3 ms 3416 KB Output is correct
93 Correct 5 ms 3844 KB Output is correct
94 Correct 5 ms 3844 KB Output is correct
95 Correct 5 ms 3844 KB Output is correct
96 Correct 4 ms 3848 KB Output is correct
97 Correct 3 ms 3668 KB Output is correct