| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1129055 | crafticat | Library (JOI18_library) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;
template<typename T>
using V = vector<T>;
#define s second
#define F0R(i,n) for(int i = 0; i < n;i++)
#define FOR(i,j,n) for(int i = j; i < n;i++)
using ll = long long;
using vi = V<int>;
int Query(const std::vector<int>& M);
void Answer(const std::vector<int>& res);
int n;
vi vis;
int test(int l, int r, int expel = -1) {
vi arr = vis;
FOR(i,l,r)
arr[i] = 1;
if (expel != -1) arr[expel] = 0;
if (arr == vis) return -1; // No changes were made
F0R(i, n)
arr[i] = !arr[i];
bool allZ = true;
F0R(i,n) {
if (arr[i]) allZ = false;
}
if (allZ) return 0;
return Query(arr);
}
int getNext(int l, int r, int x) {
if (r - l <= 1)
return l;
int mid = (l + r) / 2;
// without
vis[x] = 0;
int without = test(l, mid, x);
vis[x] = 1;
int with = test(l, mid);
if (without > with && without != -1)
return getNext(l, mid, x);
else
return getNext(mid, r, x);
}
void Solve(int N)
{
if (N == 1) {
Answer({1});
return;
}
n = N;
vi edges;
vi ans;
vis.resize(N);
F0R(i, N) {
if (test(i, i + 1) == 1)
edges.push_back(i);
}
if (edges.size() < 2) exit(5);
int last = edges[0];
ans.push_back(last + 1);
F0R(i, N - 2) {
int next = getNext(0, n, last);
last = next;
ans.push_back(next + 1);
}
ans.push_back(edges[1] + 1);
Answer(ans);
}
using namespace std;
void Solve(int N);
int myrandom (int i) { return std::rand()%i;}
namespace {
struct Judge
{
int N;
int A[1002];
int pos[1002];
bool f[1002];
int query_c;
bool answered;
void init()
{
query_c=0;
int ret=scanf("%d",&N); ret++;
answered=false;
for(int i=0;i<N;i++)ret=scanf("%d",&A[i]),pos[A[i]]=i;
}
int query(const vector<int>& M)
{
if(query_c==20000)
{
puts("Wrong Answer [3]");
exit(5);
}
if(int(M.size())!=N)
{
puts("Wrong Answer [1]");
exit(5);
}
bool all_zero=true;
for(int i=0;i<N;i++)
{
if(M[i]!=0&&M[i]!=1)
{
puts("Wrong Answer [2]");
exit(5);
}
if(M[i]==1)all_zero=false;
}
if(all_zero)
{
puts("Wrong Answer [2]");
exit(5);
}
memset(f,0,sizeof(f));
for(int i=0;i<N;i++)if(M[i])f[pos[i+1]]=true;
bool las=false;
int r=0;
for(int i=0;i<N;i++)
{
if(!las && f[i])r++;
las=f[i];
}
query_c++;
return r;
}
void answer(const vector<int>& res)
{
bool f1=true,f2=true;
if(int(res.size())!=N)
{
puts("Wrong Answer [4]");
exit(5);
}
if(answered)
{
puts("Wrong Answer [7]");
exit(5);
}
answered=true;
memset(f,0,sizeof(f));
for(int i=0;i<N;i++)
{
if(res[i]<=0||res[i]>N)
{
puts("Wrong Answer [5]");
exit(5);
exit(5);
}
if(f[res[i]])
{
puts("Wrong Answer [6]");
exit(5);
exit(5);
}
f[res[i]]=true;
}
for(int i=0;i<N;i++)
{
f1&=A[i]==res[i];
f2&=A[i]==res[N-i-1];
}
if(!f1&&!f2)
{
puts("Wrong Answer [8]");
exit(5);
}
}
void end()
{
if(!answered)puts("Wrong Answer [7]");
else printf("Accepted : %d\n",query_c);
}
}judge;
}
int Query(const vector<int>& M)
{
return judge.query(M);
}
void Answer(const vector<int>& res)
{
judge.answer(res);
}
int main()
{
judge.init();
Solve(judge.N);
judge.end();
}
//5
//4
//2
//5
//3
//1