제출 #483694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483694		gmyu	커다란 상품 (IOI17_prize)	C++14	0 / 100	5 ms	9852 KiB

prize

/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/IOI17_prize
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <string.h>
#include <set>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define ff  first
#define ss  second
#define pb  push_back
#define sz(x)   (int)(x).size()

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 200007
#define MAXE 100007

const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
    int x, y;
    int val;
    int visited;
    bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct EDGE {
    int from, to;
    ll weight;
    bool operator<(EDGE other) const { return weight < other.weight; }
};

bool debug=false;


/** since cnt(t) > cnt(t-1)^2 and cnt(1) = 1, number of prize is more than 1, 2^1, 2^2, 2^3, ...
 *  which means the sum of # of more expensive items is unique since the sum of all prize <t is less than cnt(t)
 *  make totMore = a[0] + a[1]
 *  then for i and j, if totMore[i] == totMore[j], then they are the same type
 *  we can divide and conquer to find the higher prize item (until totMore == 0)
 *  for each totMore, if a[0] on the left is the same the a[0] here, then there is no more expensive between those two
 */


#include "prize.h"
int ans=-1;
set<int> cnt[MAXV];
int leMore[MAXV];

bool divRcon(int l, int r) {
    if(l>r) return false;
    int m = (l+r)/2;
    auto a = ask(m);
    int totMore = a[0] + a[1];
    leMore[m] = a[0];
    if(totMore==0) {ans = m; return true;}

    auto it = cnt[totMore].insert(m).ff;
    if(it==cnt[totMore].begin())
        if(divRcon(l,m-1)) return true;
    else if(leMore[*prev(it)] != leMore[*it])
        if(divRcon(l, m-1)) return true;

    if(next(it)==cnt[totMore].end())
        if(divRcon(m+1,r)) return true;
    else if(leMore[*next(it)] != leMore[*it])
        if(divRcon(m+1, r)) return true;

    return false;
}
int find_best(int n) {
    divRcon(0,n-1);
    return ans;
}

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

prize.cpp: In function 'bool divRcon(int, int)':
prize.cpp:78:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   78 |     if(it==cnt[totMore].begin())
      |       ^
prize.cpp:83:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   83 |     if(next(it)==cnt[totMore].end())
      |       ^

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