oj.uz

답안 #965506

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
965506 2024-04-18T18:37:00 Z Nahian9696 커다란 상품 (IOI17_prize) C++17
0 / 100
 4 ms 3668 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 != mx){
			gems[i-1] = true;
		}
	}

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


    

    int cur_lolipop = max_gems, left, right;

    while(true) {
        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) {

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

        while(l < r) {
            int mid = (l+r)/2;

            vector<int> v = askk(mid);
            ll a = v[0];
			ll b = v[1];
			ll c = a+b;

			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;
            }
        }


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

        while(true) {
            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:112:27: warning: statement has no effect [-Wunused-value]
  112 |                 gems[mid] == true;
      |                 ~~~~~~~~~~^~~~~~~
prize.cpp:37:5: warning: variable 'mxind' set but not used [-Wunused-but-set-variable]
   37 |  ll mxind = 0;
      |     ^~~~~
prize.cpp:149:1: warning: control reaches end of non-void function [-Wreturn-type]
  149 | }
      | ^

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 4 ms 3416 KB Output is correct
3 Correct 3 ms 3668 KB Output is correct
4 Incorrect 3 ms 3592 KB Integer 200000 violates the range [0, 199999]
5 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3416 KB Output is correct
2 Correct 4 ms 3416 KB Output is correct
3 Correct 3 ms 3416 KB Output is correct
4 Incorrect 3 ms 3592 KB Integer 200000 violates the range [0, 199999]
5 Halted 0 ms 0 KB -