| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 395744 |
2021-04-28T20:19:27 Z |
Victor |
Library (JOI18_library) |
C++17 |
|
0 ms |
0 KB |
#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();
}
Compilation message
library.cpp: In function 'int binsearch(vi)':
library.cpp:7:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
7 | #define rep(i, a, b) for (int i = a; i < (b); ++i)
| ^
library.cpp:52:9: note: in expansion of macro 'rep'
52 | rep(i, take, sz(books)) nbooks.push_back(books[i]);
| ^~~
library.cpp: In function 'void Solve(int)':
library.cpp:68:23: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
68 | if(sz(queried)==n)break;
| ^
library.cpp:81:23: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
81 | if(sz(queried)==n)break;
| ^
/tmp/ccDeXNK3.o: In function `Query(std::vector<int, std::allocator<int> > const&)':
library.cpp:(.text+0x0): multiple definition of `Query(std::vector<int, std::allocator<int> > const&)'
/tmp/ccYwE60J.o:grader.cpp:(.text+0x0): first defined here
/tmp/ccDeXNK3.o: In function `Answer(std::vector<int, std::allocator<int> > const&)':
library.cpp:(.text+0x180): multiple definition of `Answer(std::vector<int, std::allocator<int> > const&)'
/tmp/ccYwE60J.o:grader.cpp:(.text+0x390): first defined here
/tmp/ccDeXNK3.o: In function `main':
library.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccYwE60J.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
