LOJ#2985. 「WC2019」I 君的商店

一道很神仙的题啊QAQ

居然是智商题……不是乱搞或者是大数据

我们可以用2N问出一个最大值是1

然后对于任意两个值\(x + y\)和\(a\)比较

如果\(x + y \leq a\)，那么其中的最小值是\(0\)

如果\(x + y \geq a\)那么其中的最大值是1

我们比较\(x\)和\(y\)的大小，总可以得到一个数的确定值

这是\(7N\)的

而如果我们直接选三个数\(x,y,a\)

用2的代价使得\(x \geq y\)

如果$x + y \leq a $

那么\(y\)必然是0

否则把现在\(a\)扔进一个序列里，\(x\)成为新的\(a\)，\(y\)成为新的\(x\)

这样的话我们会得到一个递增序列和一个单出来的值，通过二分把这个单出来的值塞进序列里，所有的1必然都在这个序列里

那么我们可以二分，找准可能的最后一个0的位置，要么这个位置和它的前一个位置是00，要么就是11，最后一位必然是1，通过这个找到最后一个0的位置，序列后面的就都是1了

#include "shop.h"

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 100005

#define ba 47

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 +c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

vector<int> line,possible;

int S[5],T[5],k,res[MAXN];

int cmp(int a,int b) {// return a >= b

    S[0] = b;T[0] = a;

    return query(S,1,T,1);

}

void Binary() {

    possible.clear();

    for(int i = -1 ; i < (int)line.size() - 1 ; i++) {

	int t = (line.size() - i - 1) ^ k ^ 1;

	if(t & 1) possible.pb(i);

    }

    int l = 0,r = possible.size() - 1;

    while(l < r) {

	int mid = (l + r + 1) >> 1;

	int x = possible[mid];

	S[0] = line[x];S[1] = line[x - 1];T[0] = line.back();

	if(query(S,2,T,1)) l = mid;

	else r = mid - 1;

    }

    int x = possible[l];

    for(int i = x + 1 ; i < line.size() ; ++i) res[line[i]] = 1;

}

void find_price(int task_id, int N, int K, int ans[]) {

    memset(res,0,sizeof(res));

    k = K;

    if(N == 1) {ans[0] = 1;return;}

    line.clear();

    if(task_id == 3) {

	if(cmp(N - 1,0)) {

	    for(int i = 0 ; i < N ; ++i) line.pb(i);

	}

	else {

	    for(int i = N - 1 ; i >= 0 ; --i) line.pb(i);

	}

    }

    else {

	int a = 0,x = 1,y;

	for(int i = 2 ; i < N ; ++i) {

	    y = i;

	    if(cmp(y,x)) swap(y,x);

	    S[0] = x;S[1] = y;T[0] = a;

	    if(query(S,2,T,1)) {//x + y <= a

	    }

	    else {

		line.pb(a);

		a = x;x = y;

	    }

	}

	line.pb(a);

	int l = 0,r = line.size() - 1;

	if(cmp(x,line[r])) line.pb(x);

	else {

	    while(l < r) {

		int mid = (l + r) >> 1;

		if(cmp(line[mid],x)) r = mid;

		else l = mid + 1;

	    }

	    line.insert(line.begin() + l,x);

	}

    }

    Binary();

    for(int i = 0 ; i < N ; ++i) {

	ans[i] = res[i];

    }

    return ;

}