Submission #483696

#	Time	Username	Problem	Language	Result	Execution time	Memory
483696		gmyu	The Big Prize (IOI17_prize)	C++14	100 / 100	53 ms	10804 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;
    vi 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;
}

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