Submission #483692

#	Time	Username	Problem	Language	Result	Execution time	Memory
483692		gmyu	The Big Prize (IOI17_prize)	C++14	Compilation error	0 ms	0 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
 */

/*
int N;
vi ask(int m){
    int a[8] = {3,2,3,1,3,3,2,3};
    vi ret(2,0);
    for(int i=0;i<m;i++) if(a[i]<a[m]) ret[0]++;
    for(int i=m+1;i<N;i++) if(a[i]<a[m]) ret[1]++;
    return ret;
}*/


//#include "prize.h"
int ans;
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((*prev(it))+1, 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, (*next(it))-1 )) return true;

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

Compilation message (stderr)

prize.cpp: In function 'bool divRcon(int, int)':
prize.cpp:82:14: error: 'ask' was not declared in this scope
   82 |     auto a = ask(m);
      |              ^~~
prize.cpp:88:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   88 |     if(it==cnt[totMore].begin())
      |       ^
prize.cpp:93:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   93 |     if(next(it)==cnt[totMore].end())
      |       ^