| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 130208 |
2019-07-14T09:02:41 Z |
RockyB |
Library (JOI18_library) |
C++17 |
|
378 ms |
4572 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 = 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);
}
// 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:7: warning: variable 'R' set but not used [-Wunused-but-set-variable]
int R = -1, L = N + 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 |
38 ms |
4344 KB |
# of queries: 1901 |
| 2 |
Correct |
39 ms |
4216 KB |
# of queries: 1920 |
| 3 |
Correct |
30 ms |
4392 KB |
# of queries: 2029 |
| 4 |
Correct |
31 ms |
4312 KB |
# of queries: 2067 |
| 5 |
Correct |
43 ms |
4344 KB |
# of queries: 2056 |
| 6 |
Correct |
42 ms |
4344 KB |
# of queries: 2045 |
| 7 |
Correct |
40 ms |
4216 KB |
# of queries: 2044 |
| 8 |
Correct |
28 ms |
4392 KB |
# of queries: 1971 |
| 9 |
Correct |
30 ms |
4312 KB |
# of queries: 2031 |
| 10 |
Correct |
27 ms |
4344 KB |
# of queries: 1171 |
| 11 |
Correct |
5 ms |
4216 KB |
# of queries: 0 |
| 12 |
Correct |
5 ms |
4344 KB |
# of queries: 2 |
| 13 |
Correct |
6 ms |
4344 KB |
# of queries: 5 |
| 14 |
Correct |
5 ms |
4344 KB |
# of queries: 9 |
| 15 |
Correct |
6 ms |
4344 KB |
# of queries: 68 |
| 16 |
Correct |
7 ms |
4216 KB |
# of queries: 155 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
4344 KB |
# of queries: 1901 |
| 2 |
Correct |
39 ms |
4216 KB |
# of queries: 1920 |
| 3 |
Correct |
30 ms |
4392 KB |
# of queries: 2029 |
| 4 |
Correct |
31 ms |
4312 KB |
# of queries: 2067 |
| 5 |
Correct |
43 ms |
4344 KB |
# of queries: 2056 |
| 6 |
Correct |
42 ms |
4344 KB |
# of queries: 2045 |
| 7 |
Correct |
40 ms |
4216 KB |
# of queries: 2044 |
| 8 |
Correct |
28 ms |
4392 KB |
# of queries: 1971 |
| 9 |
Correct |
30 ms |
4312 KB |
# of queries: 2031 |
| 10 |
Correct |
27 ms |
4344 KB |
# of queries: 1171 |
| 11 |
Correct |
5 ms |
4216 KB |
# of queries: 0 |
| 12 |
Correct |
5 ms |
4344 KB |
# of queries: 2 |
| 13 |
Correct |
6 ms |
4344 KB |
# of queries: 5 |
| 14 |
Correct |
5 ms |
4344 KB |
# of queries: 9 |
| 15 |
Correct |
6 ms |
4344 KB |
# of queries: 68 |
| 16 |
Correct |
7 ms |
4216 KB |
# of queries: 155 |
| 17 |
Correct |
338 ms |
4340 KB |
# of queries: 13975 |
| 18 |
Correct |
376 ms |
4452 KB |
# of queries: 13811 |
| 19 |
Correct |
373 ms |
4456 KB |
# of queries: 13835 |
| 20 |
Correct |
378 ms |
4520 KB |
# of queries: 13004 |
| 21 |
Correct |
349 ms |
4480 KB |
# of queries: 12304 |
| 22 |
Correct |
362 ms |
4572 KB |
# of queries: 13898 |
| 23 |
Correct |
354 ms |
4472 KB |
# of queries: 13925 |
| 24 |
Correct |
135 ms |
4324 KB |
# of queries: 6309 |
| 25 |
Correct |
377 ms |
4264 KB |
# of queries: 13633 |
| 26 |
Correct |
327 ms |
4344 KB |
# of queries: 12682 |
| 27 |
Correct |
138 ms |
4344 KB |
# of queries: 6310 |
| 28 |
Correct |
267 ms |
4444 KB |
# of queries: 9474 |
| 29 |
Correct |
273 ms |
4444 KB |
# of queries: 9463 |
| 30 |
Correct |
233 ms |
4472 KB |
# of queries: 9474 |
