| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 395744 | Victor | 도서관 (JOI18_library) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "library.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
const int INF = 1000000007;
vi dummy;
int book = 0;
uset<int> queried;
int binsearch(vi books) {
vi qvec = dummy;
qvec[book] = 1;
if (sz(books) == 1) {
qvec[books[0]] = 1;
if (Query(qvec) != 1)
return -1;
else
return books[0];
}
int take = sz(books) >> 1;
rep(i, 0, take) qvec[books[i]] = 1;
int moves = Query(qvec);
qvec[book] = 0;
vi nbooks;
if (Query(qvec) < moves)
rep(i, take, sz(books)) nbooks.push_back(books[i]);
else
rep(i, 0, take) nbooks.push_back(books[i]);
return binsearch(nbooks);
}
void Solve(int n) {
dummy.resize(n);
vi ans(n);
int rgt[n];
memset(rgt, -1, sizeof(rgt));
while (book != -1) {
queried.insert(book);
if(sz(queried)==n)break;
vi vec;
rep(i, 0, n) if (!queried.count(i)) vec.push_back(i);
int next = binsearch(vec);
rgt[book] = next;
book = next;
}
book = 0;
while (1) {
queried.insert(book);
if(sz(queried)==n)break;
vi vec;
rep(i, 0, n) if (!queried.count(i)) vec.push_back(i);
int next = binsearch(vec);
rgt[next] = book;
book = next;
}
rep(i, 0, n) {
ans[i] = book + 1;
book = rgt[book];
}
Answer(ans);
}
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(0);
}
if(int(M.size())!=N)
{
puts("Wrong Answer [1]");
exit(0);
}
bool all_zero=true;
for(int i=0;i<N;i++)
{
if(M[i]!=0&&M[i]!=1)
{
puts("Wrong Answer [2]");
exit(0);
}
if(M[i]==1)all_zero=false;
}
if(all_zero)
{
puts("Wrong Answer [2]");
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]");
exit(0);
}
if(answered)
{
puts("Wrong Answer [7]");
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]");
exit(0);
}
if(f[res[i]])
{
puts("Wrong Answer [6]");
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]");
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 main()
{
judge.init();
Solve(judge.N);
judge.end();
}