| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 130207 |
2019-07-14T09:01:27 Z |
RockyB |
Library (JOI18_library) |
C++17 |
|
431 ms |
4580 KB |
#include "library.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int)1000 + 7;
vector <int> g[MAXN];
int N;
int dp[MAXN];
int ask(int mid) {
if (~dp[mid]) return dp[mid];
vector <int> A(N);
for (int j = mid; j <= N; j++) A[j - 1] = 1;
return dp[mid] = Query(A);
}
int dp1[MAXN][MAXN];
int ask1(int i, int mid) {
if (~dp1[i][mid]) return dp1[i][mid];
// cerr << " -> " << i << ' ' << mid << endl;
vector <int> A(N);
for (int j = mid; j <= N; j++) A[j - 1] = 1;
A[i - 1] = 1;
return dp1[i][mid] = Query(A);
}
void Solve(int n) {
N = n;
// Copy
memset(dp, -1, sizeof(dp));
memset(dp1, -1, sizeof(dp1));
for (int i = 1; i <= N; i++) {
int R = -1, L = N + 1;
{
int l = i + 1, r = N, add = -1;
while (l <= r) {
int mid = l + r >> 1;
int c1 = ask(mid);
int c2 = ask1(i, mid);
if (c1 < c2) r = mid - 1;
else add = mid, l = mid + 1;
}
if (add != -1) {
g[i].push_back(add);
g[add].push_back(i);
R = add - 1;
}
}
{
int l = i + 1, r = R, add = -1;
while (l <= r) {
int mid = l + r >> 1;
int c1 = ask(mid);
int c2 = ask1(i, mid);
if (c1 <= c2) r = mid - 1;
else add = mid, l = mid + 1;
}
if (add != -1) {
g[i].push_back(add);
g[add].push_back(i);
}
// cerr << i << ' ' << add << endl;
}
}
int v = -1, p = -1;
vector <int> ans;
for (int i = 1; i <= N; i++) {
// cerr << i << " -> " << g[i].size() << endl;
if (g[i].size() <= 1) {
v = i;
break;
}
}
while (ans.size() < N) {
ans.push_back(v);
for (auto it : g[v]) {
if (it != p) {
p = v;
v = it;
break;
}
}
}
// for (auto it : ans) cerr << it << ' ';
Answer(ans);
}
Compilation message
library.cpp: In function 'void Solve(int)':
library.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
library.cpp:55:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
library.cpp:36:15: warning: unused variable 'L' [-Wunused-variable]
int R = -1, L = N + 1;
^
library.cpp:79:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ans.size() < N) {
~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
4344 KB |
# of queries: 1990 |
| 2 |
Correct |
40 ms |
4312 KB |
# of queries: 2015 |
| 3 |
Correct |
42 ms |
4216 KB |
# of queries: 2131 |
| 4 |
Correct |
32 ms |
4392 KB |
# of queries: 2162 |
| 5 |
Correct |
42 ms |
4400 KB |
# of queries: 2136 |
| 6 |
Correct |
40 ms |
4316 KB |
# of queries: 2116 |
| 7 |
Correct |
33 ms |
4344 KB |
# of queries: 2133 |
| 8 |
Correct |
37 ms |
4344 KB |
# of queries: 2057 |
| 9 |
Correct |
44 ms |
4316 KB |
# of queries: 2123 |
| 10 |
Correct |
19 ms |
4316 KB |
# of queries: 1231 |
| 11 |
Correct |
5 ms |
4216 KB |
# of queries: 0 |
| 12 |
Correct |
5 ms |
4216 KB |
# of queries: 2 |
| 13 |
Correct |
5 ms |
4216 KB |
# of queries: 5 |
| 14 |
Correct |
5 ms |
4264 KB |
# of queries: 9 |
| 15 |
Correct |
6 ms |
4344 KB |
# of queries: 75 |
| 16 |
Correct |
7 ms |
4216 KB |
# of queries: 163 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
4344 KB |
# of queries: 1990 |
| 2 |
Correct |
40 ms |
4312 KB |
# of queries: 2015 |
| 3 |
Correct |
42 ms |
4216 KB |
# of queries: 2131 |
| 4 |
Correct |
32 ms |
4392 KB |
# of queries: 2162 |
| 5 |
Correct |
42 ms |
4400 KB |
# of queries: 2136 |
| 6 |
Correct |
40 ms |
4316 KB |
# of queries: 2116 |
| 7 |
Correct |
33 ms |
4344 KB |
# of queries: 2133 |
| 8 |
Correct |
37 ms |
4344 KB |
# of queries: 2057 |
| 9 |
Correct |
44 ms |
4316 KB |
# of queries: 2123 |
| 10 |
Correct |
19 ms |
4316 KB |
# of queries: 1231 |
| 11 |
Correct |
5 ms |
4216 KB |
# of queries: 0 |
| 12 |
Correct |
5 ms |
4216 KB |
# of queries: 2 |
| 13 |
Correct |
5 ms |
4216 KB |
# of queries: 5 |
| 14 |
Correct |
5 ms |
4264 KB |
# of queries: 9 |
| 15 |
Correct |
6 ms |
4344 KB |
# of queries: 75 |
| 16 |
Correct |
7 ms |
4216 KB |
# of queries: 163 |
| 17 |
Correct |
424 ms |
4448 KB |
# of queries: 14554 |
| 18 |
Correct |
404 ms |
4344 KB |
# of queries: 14400 |
| 19 |
Correct |
431 ms |
4396 KB |
# of queries: 14431 |
| 20 |
Correct |
374 ms |
4580 KB |
# of queries: 13523 |
| 21 |
Correct |
332 ms |
4452 KB |
# of queries: 12766 |
| 22 |
Correct |
360 ms |
4444 KB |
# of queries: 14474 |
| 23 |
Correct |
413 ms |
4472 KB |
# of queries: 14534 |
| 24 |
Correct |
150 ms |
4344 KB |
# of queries: 6612 |
| 25 |
Correct |
414 ms |
4472 KB |
# of queries: 14216 |
| 26 |
Correct |
362 ms |
4324 KB |
# of queries: 13216 |
| 27 |
Correct |
136 ms |
4352 KB |
# of queries: 6600 |
| 28 |
Correct |
265 ms |
4344 KB |
# of queries: 9474 |
| 29 |
Correct |
276 ms |
4452 KB |
# of queries: 9463 |
| 30 |
Correct |
262 ms |
4572 KB |
# of queries: 9474 |
