이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
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 val[N];
LL mySkim(int pos)
{
if (!used[pos])
{
used[pos] = 1;
val[pos] = skim(pos);
}
return val[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;
a[m] = 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++)
a[i] = mySkim(i);
for (int i = pos - 1; i >= pos - k; i--)
a[i] = mySkim(i);
for (int i = 1; i <= n; i++)
pr[i] = pr[i - 1] + a[i];
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 - k + i] - pr[pos - k]))
{
ans = lr(i + 1, k);
vector<int> x = lr(pos - k + 1, pos - k + i);
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
*/
컴파일 시 표준 에러 (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++)
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |