Submission #436853

#	Time	Username	Problem	Language	Result	Execution time	Memory
436853		davitmarg	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	3 ms	1216 KiB

books

/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <random>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair    
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;

#ifndef death
#include "books.h"
#endif // death


const int N = 500005;

#ifdef death

LL A[N];

LL skim(int i)
{
	cout << "? " << i << endl;
	LL res = A[i];
	//cin >> res;
	return res;
}

void answer(vector<int> v)
{
	cout << "!";
	for (int i = 0; i < v.size(); i++)
		cout << " " << v[i];
	cout << endl;
}

void impossible()
{
	cout << "! -1" << endl;
}

#endif

int rnd()
{
	return (rand() << 32) + rand();
}

int rnd(int l, int r)
{
	int d = r - l + 1;
	return l + rnd() % d;
}


int n, k, s;
LL X, a[N], sum, pr[N];
vector<int> ans;
int used[N];

LL mySkim(int pos)
{
	if (!used[pos])
	{
		used[pos] = 1;
		a[pos] = skim(pos);
	}
	return a[pos];
}

vector<int> lr(int l, int r)
{
	vector<int> res;
	for (int i = l; i <= r; i++)
		res.push_back(i);
	return res;
}

LL get(int l, int r)
{
	LL p = r - l + 1ll;
	LL sum = 0;
	int steps = min(70, r - l + 1);
	int d = p / steps;
	for (int i = 0; i < steps; i++)
	{
		sum += skim(r - d * i) * p;
	}
	sum /= steps;
	return sum;
}

bool check(LL val)
{
	return (val >= X && val <= X + X);
}

void solve(int NN, int K, long long A, int S)
{
	n = NN;
	k = K;
	X = A;
	s = S;

	int l = k, r = n, m, pos = n + 1;

	while (l <= r)
	{
		m = (l + r) / 2;
		mySkim(m);
		if (a[m] >= X)
		{
			pos = m;
			r = m - 1;
		}
		else
			l = m + 1;
	}

	if (pos < k)
	{
		impossible();
		return;
	}


	for (int i = 1; i <= k; i++)
		mySkim(i);		

	for (int i = pos - 1; i >= pos - k && i >= 1; i--)
		mySkim(i);

	for (int i = 1; i <= n; i++)
		pr[i] = pr[i - 1] + a[i];

	if(pos<=n)
	if (check(pr[k - 1] + a[pos]))
	{
		ans = lr(1, k - 1);
		ans.push_back(pos);
		answer(ans);
		return;
	}

	if (check(pr[k]))
	{
		ans = lr(1, k);
		answer(ans);
		return;
	}

	pos--;

	if (pos < k)
	{
		impossible();
		return;
	}

	if (check(pr[pos] - pr[pos - k]))
	{
		ans = lr(pos-k+1, pos);
		answer(ans);
		return;
	}

	for (int i = 1; i < k; i++)
	{
		if (check(pr[k] - pr[i] + pr[pos] - pr[pos - i]))
		{
			ans = lr(i + 1, k);
			vector<int> x = lr(pos - i + 1, pos);
			for (int j = 0; j < x.size(); j++)
				ans.push_back(x[j]);
			answer(ans);
			return;
		}
	}

	impossible();
}


#ifdef death

int main()
{
	fastIO;
	int nn, kk, aa;
	cin >> nn >> kk >> aa;
	for (int i = 1; i <= nn; i++)
		cin >> A[i];
	solve(nn, kk, aa, 100);
	return 0;
}


#endif // death

/*


8 3 110
1 3 5 10 40 60 70 105


*/

Compilation message (stderr)

books.cpp: In function 'int rnd()':
books.cpp:67:17: warning: left shift count >= width of type [-Wshift-count-overflow]
   67 |  return (rand() << 32) + rand();
      |          ~~~~~~~^~~~~
books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:194:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |    for (int j = 0; j < x.size(); j++)
      |                    ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20