| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 969298 |
2024-04-24T22:23:57 Z |
Tob |
Zagonetka (COI18_zagonetka) |
C++14 |
|
47 ms |
700 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;
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 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;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> p[i]; p[i]--;
pos[p[i]] = i;
}
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);
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:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i = 1; i < sk.size(); i++) {
| ~~^~~~~~~~~~~
zagonetka.cpp: In function 'void G(int, int, std::vector<int>)':
zagonetka.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int i = 1; i < sk.size(); i++) {
| ~~^~~~~~~~~~~
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:124:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
124 | for (int i = 0; i < n; i++) cout << resa[i]+1 << " "; cout << endl;
| ^~~
zagonetka.cpp:124:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
124 | for (int i = 0; i < n; i++) cout << resa[i]+1 << " "; cout << endl;
| ^~~~
zagonetka.cpp:125:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
125 | for (int i = 0; i < n; i++) cout << resb[i]+1 << " "; cout << endl;
| ^~~
zagonetka.cpp:125:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
125 | for (int i = 0; i < n; i++) cout << resb[i]+1 << " "; cout << endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
692 KB |
not a valid command |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
596 KB |
not a valid command |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
700 KB |
not a valid command |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
452 KB |
not a valid command |
| 2 |
Halted |
0 ms |
0 KB |
- |
