# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1132240 | Wendidiask | Library (JOI18_library) | C++20 | 0 ms | 0 KiB |
/*
:---:--:--::::::--:-:----:
::-:::. ::-:::
.* -===.. :---
.-+*##=-------====-: :--:
:+##=.* -= :=+- .-=:
.+++-. :- -=. .=+- .--.
.++=- + -= :*- :-.
+*+- :- -=. -*: :=:
#*: * -=. +- .=
=:%+ -: -=. +- --
-%: * -=. *: +.
:%-.. =. -=. # -:
:=# .. + -=. == -=
---+ . = -=. .# .+
-: == . = :------::------:.-=. % .=
:- == .=. ---:. :--#+. .% :-
= .* .+.. :=- :++ -+ =:
+ #. + -=: :*%-*: *
:= :# :=:= . :-----: =+-+ .+
* -* *=- . .- :::::::. :* .#+. +
:- -+ :#. --::-----: :* ++= .-
+ :*. *. .:::::*%: ++ +.-=. +
+ -#**----: .= -*. + -= =
* +.#=+: + . .=+: =. -=. =
= -+ :++: + .. .=+= .= -=. -
= %- :====-:. =. .:--===- * -=. -
+ +-- .:--==#==-:.= + -=. =
* + * =. : .= -=. =
+ = * + = -=. +
:- = .= =: = -=. .-
* + =: * * -=. +
:- .+ =- :- .+ -=. .+
* * := * := -= *
= :- =: .- .=: -=. =:
-: * .=- + .=- -= :-
=: -: --: :- :--: -=. .=
=:+ ----. * :---. -= .+
--=*----------------------=*+=--=+--=+*+------------------------------------------------%+:.
:: := +:- -- :.
.=. =.
-= -=
.=: .=.
.=: .+:
:-- :-:
-- -=.
:--. --:
:--: .--:
.-:-: ::--.
:----. .:----
.:::::::::-::::::--::::::::.
*/
// Hello this is Tyx2019's clone
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cerr << #x << " is " << x << "\n"
#define hehe ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repb(i, a, b) for (int i = b; i >= a; i--)
#define pii pair<int, int>
#define linebreak cout << "---------------------------------------------------------\n"
#define f first
#define s second
#define pb push_back
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// good luck
const int MS = 2e5+5, mod = 1e9+9, INF = INT_MAX, blk = 400;
int good = 1;
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]"); good = 0;
exit(0);
}
if(int(M.size())!=N)
{
puts("Wrong Answer [1]"); good= 0;
exit(0);
}
bool all_zero=true;
for(int i=0;i<N;i++)
{
if(M[i]!=0&&M[i]!=1)
{
puts("Wrong Answer [2]"); good= 0;
exit(0);
}
if(M[i]==1)all_zero=false;
}
if(all_zero)
{
puts("Wrong Answer [2]"); good = 0;
exit(0);
}
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==false&&f[i]==true)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]"); good = 0;
exit(0);
}
if(answered)
{
puts("Wrong Answer [7]"); good = 0;
exit(0);
}
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]"); good = 0;
exit(0);
}
if(f[res[i]])
{
puts("Wrong Answer [6]"); good = 0;
exit(0);
}
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]"); good = 0;
exit(0);
}
}
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 vis[MS];
void Solve(int n) {
vector<int> v, ans;
if (n == 1) {
ans.pb(1);
Answer(ans); return;
}
int last = -1;
for (int i = 0; i < n; i++) {v.pb(1); vis[i] = 0;}
for (int i = 0; i < n; i++) {
v[i] = 0;
if (Query(v) == 1) {ans.pb(i+1); vis[i] = 1; last = i; break;}
v[i] = 1;
}
//debug(last+1);
// determined first element
for (int i = 1; i < n; i++) {
vector<int> res;
for (int j = 0; j < n; j++) {
if (!vis[j]) res.pb(1);
else res.pb(0);
}
//for (auto it : res) cout << it << " ";
//cout << '\n';
int low = 0, high = n-1;
while (low < high) {
int mid = (low+high)>>1;
vector<int> templ = res;
for (int j = 0; j < n; j++) {
if (low <= j and j <= mid) continue;
templ[j] = 0;
}
int prev = 0;
for (int j = 0; j < n; j++) if (templ[j] == 1) {
prev = Query(templ);
}
templ[last] = 1;
int next = Query(templ);
//cout << low << " " << mid << ": ";
//for (auto it : templ) cout << it << " ";
//debug(prev); debug(next);
//cout << '\n';
if (prev >= next) high = mid;
else low = mid+1;
}
//debug(low+1);
vis[low] = 1;
ans.pb(low+1);
last = low;
}
Answer(ans);
}
int main()
{
//int tc; cin >> tc;
//for (int i = 1; i <= tc; i++) {
//cout << i << ": ";
judge.init();
Solve(judge.N);
judge.end();
//if (good == 0) return 69;
//}
}
#endif