제출 #821173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
821173		vjudge1	커다란 상품 (IOI17_prize)	C++17	90 / 100	132 ms	19092 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;



int find_best(int n){
    int mx = -1 , i , j , m , s , f , l , r , k , c , y , x;
    map<int,int>mp[2];
    vector<pair<int,int>> v;
    for(i = 0; i < n; i++)
        mp[0][i] = mp[1][i] = -1;
    for(i = 0; i < min(n, 700); i++){
        vector<int>gt = ask(i);
        mp[0][i] = gt[0];
        mp[1][i] = gt[1];
        v.push_back({gt[0] + gt[1] , i});
        if((gt[0] + gt[1]) == 0)
            return i;
        if((gt[0] + gt[1]) >= mx)
                mx = gt[0] + gt[1] , x = gt[0] ,  k = i;
    }

    while(k < n){
        l = k;
        r = n - 1;
        m = l + 20;
        f = 0;
        if((m + 2) < n){
            vector<int>gp;
            if(mp[0][m] == -1)
                gp = ask(m);
            else
                gp.push_back(mp[0][m]) , gp.push_back(mp[1][m]);
            int sum = gp[0] + gp[1];
            if(sum == 0)
                return m;
            if(!(sum == mx && (gp[0] == x))){
                f = 1;
                while(true){
                    vector<int>gp;
                    if(mp[0][l + 1] == -1)
                        gp = ask(l + 1);
                    else
                        gp.push_back(mp[0][l + 1]) , gp.push_back(mp[1][l + 1]);
                    int sum = gp[0] + gp[1];
                    if(sum == 0)
                        return (l + 1);
                    if((sum == mx && (gp[0] == x))){
                       l++;
                    }else {
                    x = gp[0];
                    k = l;
                    break;
                    }
            }
        }
        }
        if(f == 0)
        while(l != r){
            m = (l + r + 1) / 2;
            vector<int>gt;
            if(mp[0][m] == -1)
                gt = ask(m);
            else
                gt.push_back(mp[0][m]) , gt.push_back(mp[1][m]);
            mp[0][m] = gt[0];
            mp[1][m] = gt[1];
            int sum = gt[0] + gt[1];
            if(sum == 0)
                return m;
            if(sum == mx && (gt[0] == x)){
                l =  m;
            }else {
                r = m - 1;
            }
        }
        k = l + 1;
        while(k < n){
            vector<int>gt;
            if(mp[0][k] == -1)
            gt = ask(k);
            else
                gt.push_back(mp[0][k]) , gt.push_back(mp[1][k]);
            mp[0][k] = gt[0];
            mp[1][k] = gt[1];
            int sum = gt[0] + gt[1];
            x = gt[0];
            if(sum == 0)
                return k;
            if(sum < mx)
                v.push_back({sum , k});
            else
                break;
            k++;
        }
    }
    sort(v.begin() , v.end());
    return v[0].second;
}

컴파일 시 표준 에러 (stderr) 메시지

prize.cpp: In function 'int find_best(int)':
prize.cpp:10:23: warning: unused variable 'j' [-Wunused-variable]
   10 |     int mx = -1 , i , j , m , s , f , l , r , k , c , y , x;
      |                       ^
prize.cpp:10:31: warning: unused variable 's' [-Wunused-variable]
   10 |     int mx = -1 , i , j , m , s , f , l , r , k , c , y , x;
      |                               ^
prize.cpp:10:51: warning: unused variable 'c' [-Wunused-variable]
   10 |     int mx = -1 , i , j , m , s , f , l , r , k , c , y , x;
      |                                                   ^
prize.cpp:10:55: warning: unused variable 'y' [-Wunused-variable]
   10 |     int mx = -1 , i , j , m , s , f , l , r , k , c , y , x;
      |                                                       ^
prize.cpp:74:26: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |             if(sum == mx && (gt[0] == x)){
      |                ~~~~~~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 70 / 80