| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 469612 |
2021-09-01T12:41:58 Z |
aZvezda |
Library (JOI18_library) |
C++14 |
|
60 ms |
296 KB |
#include <cstdio>
#include <vector>
#include "library.h"
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "
const int MAX_N = 1e3 + 10;
set<int> lft;
bool used[MAX_N];
vector<int> load(int cnt, int n) {
vector<int> ret(n, 0);
for(auto it : lft) {
if(cnt <= 0) {break;}
cnt --;
ret[it - 1] = 1;
}
return ret;
}
int getm(int m) {
for(auto it : lft) {
m --;
if(m <= 0) {
return it;
}
}
return -1;
}
void Solve(int n) {
vector<int> ans;
for(int i = 1; i <= n; i ++) {
lft.insert(i);
}
lft.erase(1);
int l = 0, r = lft.size();
while(l < r - 1) {
int m = (l + r) / 2ll;
auto quer = load(m, n);
auto ans1 = Query(quer);
quer[0] = 1;
auto ans2 = Query(quer);
if(ans1 < ans2) {
l = m;
} else {
r = m;
}
}
int now = getm(r);
vector<int> ret = {1, now};
lft.erase(now);
while(ret.size() < n) {
auto curr = ret.back();
int l = 0, r = lft.size();
while(l < r - 1) {
int m = (l + r) / 2ll;
auto quer = load(m, n);
auto ans1 = Query(quer);
quer[curr - 1] = 1;
auto ans2 = Query(quer);
if(ans1 < ans2) {
l = m;
} else {
r = m;
}
}
auto quer = load(r, n);
auto ans1 = Query(quer);
quer[curr - 1] = 1;
auto ans2 = Query(quer);
if(ans1 < ans2) {
break;
} else {
int now = getm(r);
ret.push_back(now);
lft.erase(now);
}
}
reverse(ret.begin(), ret.end());
while(ret.size() < n) {
auto curr = ret.back();
int l = 0, r = lft.size();
while(l < r - 1) {
int m = (l + r) / 2ll;
auto quer = load(m, n);
auto ans1 = Query(quer);
quer[curr - 1] = 1;
auto ans2 = Query(quer);
if(ans1 < ans2) {
l = m;
} else {
r = m;
}
}
auto quer = load(r, n);
auto ans1 = Query(quer);
quer[curr - 1] = 1;
auto ans2 = Query(quer);
if(ans1 < ans2) {
break;
} else {
int now = getm(r);
ret.push_back(now);
lft.erase(now);
}
}
Answer(ret);
}
Compilation message
library.cpp: In function 'void Solve(int)':
library.cpp:72:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
72 | while(ret.size() < n) {
| ~~~~~~~~~~~^~~
library.cpp:109:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
109 | while(ret.size() < n) {
| ~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
200 KB |
# of queries: 2776 |
| 2 |
Correct |
54 ms |
296 KB |
# of queries: 2780 |
| 3 |
Correct |
48 ms |
200 KB |
# of queries: 2924 |
| 4 |
Correct |
59 ms |
200 KB |
# of queries: 2922 |
| 5 |
Correct |
55 ms |
200 KB |
# of queries: 2906 |
| 6 |
Correct |
60 ms |
200 KB |
# of queries: 2912 |
| 7 |
Correct |
48 ms |
200 KB |
# of queries: 2914 |
| 8 |
Correct |
41 ms |
200 KB |
# of queries: 2802 |
| 9 |
Correct |
32 ms |
200 KB |
# of queries: 2906 |
| 10 |
Correct |
30 ms |
200 KB |
# of queries: 1728 |
| 11 |
Incorrect |
0 ms |
200 KB |
Wrong Answer [4] |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
200 KB |
# of queries: 2776 |
| 2 |
Correct |
54 ms |
296 KB |
# of queries: 2780 |
| 3 |
Correct |
48 ms |
200 KB |
# of queries: 2924 |
| 4 |
Correct |
59 ms |
200 KB |
# of queries: 2922 |
| 5 |
Correct |
55 ms |
200 KB |
# of queries: 2906 |
| 6 |
Correct |
60 ms |
200 KB |
# of queries: 2912 |
| 7 |
Correct |
48 ms |
200 KB |
# of queries: 2914 |
| 8 |
Correct |
41 ms |
200 KB |
# of queries: 2802 |
| 9 |
Correct |
32 ms |
200 KB |
# of queries: 2906 |
| 10 |
Correct |
30 ms |
200 KB |
# of queries: 1728 |
| 11 |
Incorrect |
0 ms |
200 KB |
Wrong Answer [4] |
| 12 |
Halted |
0 ms |
0 KB |
- |
