#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
const int N = 110;
vector<int> g[N], gr[N];
priority_queue<int, vector<int>, greater<int> > pq;
priority_queue<int> PQ;
int per[N], qur[N], mrk[N], in[N], n, loc[N], out[N];
bool was;
void dfs(int v){
if (was) return;
mrk[v] = 1;
for (int u : g[v]){
if (was) return;
if (mrk[u] == 0)
dfs(u); else
if (mrk[u] == 1){
was = 1;
return;
}
}
mrk[v] = 2;
}
void prit(){
for (int i = 1; i <= n; i++){
cout << qur[i];
if (i == n)
cout << endl;
else cout << " ";
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
// freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> per[i];
loc[per[i]] = i;
}
int cnt_steps = 0;
for (int vl = 2; vl <= n; vl++)
for (int pr = vl - 1; pr > 0; pr--){
gr[loc[pr]].PB(loc[vl]);
g[loc[vl]].PB(loc[pr]);
for (int i = 1; i <= n; i++) {
qur[i] = per[i];
mrk[i] = 0;
}
was = 0;
for (int i = pr; i <= vl && !was; i++){
if (mrk[loc[i]]) continue;
dfs(loc[i]);
}
if (was){
gr[loc[pr]].pop_back();
g[loc[vl]].pop_back();
continue;
}
for (int i = pr; i <= vl; i++){
in[loc[i]] = 0;
for (int u : gr[loc[i]])
if (per[u] >= pr)
in[loc[i]]++;
if (in[loc[i]] == 0)
pq.push(loc[i]);
}
int cur = pr;
while (sz(pq) > 0){
int v = pq.top(); pq.pop();
qur[v] = cur++;
for (int u : g[v]){
if (per[u] < pr) continue;
in[u]--;
if (in[u] == 0)
pq.push(u);
}
}
cout << "query";
for (int i = 1; i <= n; i++)
cout << " " << qur[i];
cout << endl;
int res; cin >> res;
gr[loc[pr]].pop_back();
g[loc[vl]].pop_back();
if (res == 0){
cnt_steps++;
g[loc[pr]].PB(loc[vl]);
gr[loc[vl]].PB(loc[pr]);
}
// delete fictive edges
}
if (n > 6)
assert(cnt_steps == 1);
// n = 61;
//
// g[35].PB(25);
// gr[25].PB(35);
cout << "end" << endl;
for (int i = 1; i <= n; i++){
out[i] = sz(g[i]);
if (out[i] == 0)
PQ.push(i);
}
int cur = n;
while (sz(PQ) > 0){
int v = PQ.top(); PQ.pop();
qur[v] = cur--;
for (int u : gr[v]){
out[u]--;
if (out[u] == 0)
PQ.push(u);
}
}
prit();
for (int i = 1; i <= n; i++){
in[i] = sz(gr[i]);
if (in[i] == 0)
PQ.push(i);
}
fill(qur + 1, qur + n + 1, -1);
cur = 1;
while (sz(PQ) > 0){
int v = PQ.top(); PQ.pop();
qur[v] = cur++;
for (int u : g[v]){
in[u]--;
if (in[u] == 0)
PQ.push(u);
}
}
// assert(qur[35] < qur[25]);
prit();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
304 KB |
Output is correct |
2 |
Correct |
38 ms |
384 KB |
Output is correct |
3 |
Correct |
41 ms |
384 KB |
Output is correct |
4 |
Correct |
38 ms |
384 KB |
Output is correct |
5 |
Correct |
15 ms |
400 KB |
Output is correct |
6 |
Correct |
44 ms |
384 KB |
Output is correct |
7 |
Correct |
9 ms |
384 KB |
Output is correct |
8 |
Correct |
10 ms |
288 KB |
Output is correct |
9 |
Correct |
32 ms |
384 KB |
Output is correct |
10 |
Correct |
19 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
6 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
97 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |