| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 969437 |
2024-04-25T07:04:44 Z |
Tob |
Zagonetka (COI18_zagonetka) |
C++14 |
|
3000 ms |
1196 KB |
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef pair <ll, ll> pii;
const int N = 107;
int n, cur;
int p[N], pos[N], bio[N], ed[N][N], col[N], ins[N], resa[N], resb[N];
vector <pii> v, oe;
vector <int> adj[N], radj[N];
int Ask() {
cout << "query ";
for (int i = 0; i < n; i++) cout << col[i]+1 << " "; cout << endl;
int o; cin >> o; return o;
// int ok = 1;
// int cnt[N] = {0};
// for (int i = 0; i < n; i++) cnt[col[i]]++;
// for (int i = 0; i < n; i++) if (cnt[i] != 1) ok = 0;
// if (!ok) exit(0);
// for (auto it : oe) if (col[it.F] > col[it.S]) return 0;
// return 1;
}
int dfs(int x) {
bio[x] = 1;
for (auto y : adj[x]) {
if (bio[y] == 2) continue;
if (bio[y] == 1) return 1;
if (dfs(y)) return 1;
}
col[x] = cur--;
bio[x] = 2;
return 0;
}
void go(int x) {ins[x] = 1; for (auto y : adj[x]) go(y);}
void rgo(int x) {ins[x] = 1; for (auto y : radj[x]) rgo(y);}
void F(int l, int r, vector <int> sk) {
if (l > r) return;
if (l == r) {
resa[sk[0]] = l;
return;
}
memset(ins, 0, sizeof ins); go(sk[0]);
vector <int> nea, neb;
for (int i = 1; i < sk.size(); i++) {
if (ins[sk[i]]) nea.pb(sk[i]);
else neb.pb(sk[i]);
}
resa[sk[0]] = l+nea.size();
F(l, resa[sk[0]]-1, nea);
F(resa[sk[0]]+1, r, neb);
}
void G(int l, int r, vector <int> sk) {
if (l > r) return;
if (l == r) {
resb[sk[0]] = l;
return;
}
memset(ins, 0, sizeof ins); rgo(sk[0]);
vector <int> nea, neb;
for (int i = 1; i < sk.size(); i++) {
if (ins[sk[i]]) nea.pb(sk[i]);
else neb.pb(sk[i]);
}
resb[sk[0]] = r-nea.size();
G(l, resb[sk[0]]-1, neb);
G(resb[sk[0]]+1, r, nea);
}
int main () {
// FIO;
// int q;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> p[i]; p[i]--;
pos[p[i]] = i;
}
// for (int i = 0; i < q; i++) {
// int x, y; cin >> x >> y; x--; y--;
// oe.pb({x, y});
// }
for (int j = 1; j < n; j++) {
for (int i = 0; i+j < n; i++) {
adj[pos[i+j]].pb(pos[i]);
for (int k = 0; k < n; k++) col[k] = p[k];
for (int k = i; k <= i+j; k++) {
for (int l = i; l <= i+j; l++) {
if (l == k) continue;
if (ed[pos[k]][pos[l]]) adj[pos[k]].pb(pos[l]);
}
}
cur = i+j;
int ok = 0;
for (int k = i; k <= i+j; k++) if (!bio[pos[k]]) {
if (dfs(pos[k])) {
ok = 1;
break;
}
}
if (ok) {
ed[pos[i]][pos[i+j]] = 1;
v.pb({pos[i], pos[i+j]});
}
else {
if (!Ask()) {
ed[pos[i]][pos[i+j]] = 1;
v.pb({pos[i], pos[i+j]});
}
}
memset(bio, 0, sizeof bio);
memset(col, 0, sizeof col);
for (int k = 0; k < n; k++) adj[k].clear();
}
}
for (auto it : v) {
radj[it.F].pb(it.S);
adj[it.S].pb(it.F);
}
vector <int> tmp(n);
for (int i = 0; i < n; i++) tmp[i] = i;
F(0, n-1, tmp);
G(0, n-1, tmp);
cout << "end" << endl;
for (int i = 0; i < n; i++) cout << resa[i]+1 << " "; cout << endl;
for (int i = 0; i < n; i++) cout << resb[i]+1 << " "; cout << endl;
return 0;
}
Compilation message
zagonetka.cpp: In function 'int Ask()':
zagonetka.cpp:23:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
23 | for (int i = 0; i < n; i++) cout << col[i]+1 << " "; cout << endl;
| ^~~
zagonetka.cpp:23:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
23 | for (int i = 0; i < n; i++) cout << col[i]+1 << " "; cout << endl;
| ^~~~
zagonetka.cpp: In function 'void first(int, int, std::vector<int>)':
zagonetka.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int i = 1; i < sk.size(); i++) {
| ~~^~~~~~~~~~~
zagonetka.cpp: In function 'void G(int, int, std::vector<int>)':
zagonetka.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i = 1; i < sk.size(); i++) {
| ~~^~~~~~~~~~~
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:138:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
138 | for (int i = 0; i < n; i++) cout << resa[i]+1 << " "; cout << endl;
| ^~~
zagonetka.cpp:138:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
138 | for (int i = 0; i < n; i++) cout << resa[i]+1 << " "; cout << endl;
| ^~~~
zagonetka.cpp:139:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
139 | for (int i = 0; i < n; i++) cout << resb[i]+1 << " "; cout << endl;
| ^~~
zagonetka.cpp:139:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
139 | for (int i = 0; i < n; i++) cout << resb[i]+1 << " "; cout << endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
448 KB |
Output is correct |
| 3 |
Correct |
0 ms |
444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
444 KB |
Output is correct |
| 7 |
Correct |
0 ms |
440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
444 KB |
Output is correct |
| 2 |
Correct |
16 ms |
444 KB |
Output is correct |
| 3 |
Correct |
20 ms |
424 KB |
Output is correct |
| 4 |
Correct |
19 ms |
448 KB |
Output is correct |
| 5 |
Correct |
5 ms |
448 KB |
Output is correct |
| 6 |
Correct |
26 ms |
680 KB |
Output is correct |
| 7 |
Correct |
3 ms |
696 KB |
Output is correct |
| 8 |
Correct |
3 ms |
700 KB |
Output is correct |
| 9 |
Correct |
21 ms |
448 KB |
Output is correct |
| 10 |
Correct |
8 ms |
684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
440 KB |
Output is correct |
| 3 |
Correct |
3 ms |
704 KB |
Output is correct |
| 4 |
Correct |
3 ms |
956 KB |
Output is correct |
| 5 |
Correct |
1 ms |
444 KB |
Output is correct |
| 6 |
Correct |
2 ms |
468 KB |
Output is correct |
| 7 |
Correct |
2 ms |
704 KB |
Output is correct |
| 8 |
Correct |
3 ms |
956 KB |
Output is correct |
| 9 |
Correct |
3 ms |
700 KB |
Output is correct |
| 10 |
Correct |
2 ms |
700 KB |
Output is correct |
| 11 |
Correct |
3 ms |
700 KB |
Output is correct |
| 12 |
Correct |
2 ms |
440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
944 KB |
Output is correct |
| 2 |
Correct |
53 ms |
696 KB |
Output is correct |
| 3 |
Correct |
42 ms |
1196 KB |
Output is correct |
| 4 |
Execution timed out |
3089 ms |
816 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
