#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
int s[101], l[101];
int p[101];
int mat[101][101];
int pos[101];
int n;
void dfs(int x,int &num,int *vt,vector<int> edge[101]) {
vt[x] = num++;
for (auto nxt : edge[x]) {
if(vt[nxt]==0)
dfs(nxt, num, vt, edge);
}
}
int tp_sort(queue<int> &q,int *vt,int *ind,vector<int> edge[101]) {
int vis = 0;
int s = 1;
while (q.size()) {
int u= q.front(); q.pop();
vt[u] = s++;
++vis;
for (auto v : edge[u]) {
if (--ind[v]==0)
q.push(v);
}
}
return vis;
}
void qry(int x,int y) {//chk pos[x]->pos[y]
//inv edge ok -> no condition
//inv edge no -> there is condition
//cycle -> there is cond.(inclusive indirect)
vector<int> edge[101];
vector<int> loc;
int ind[101] = { 0 };
int myp[101] = {};
for (int i = 1; i <= n; ++i) myp[i] = p[i];
for (int i = x; i <= y; ++i) loc.push_back(pos[i]);
for (int i = 0; i < loc.size(); ++i) {
for (int j = i + 1; j < loc.size(); ++j) {
if (mat[loc[i]][loc[j]]) {
edge[loc[i]].push_back(loc[j]);
++ind[loc[j]];
}
}
}
edge[pos[y]].push_back(pos[x]);//inv edge
++ind[pos[x]];
queue<int> q;
for (auto v : loc) {
if (ind[v] == 0) q.push(v);
}
if (y - x + 1 == tp_sort(q, myp, ind, edge)) {
for (auto v : loc) myp[v]+=x-1;
int i;
for (printf("query"), i = 1; i <= n; ++i) printf(" %d",myp[i]);
printf("\n"); fflush(stdout);
scanf("%d",&i);
if (i) return;
}
//cycle chk
mat[pos[x]][pos[y]] = 1;
}
int main() {
int i;
for (scanf("%d", &n), i = 1; i <= n; ++i) {
scanf("%d", p + i);
pos[p[i]] = i;
}
for (int range = 1; range < n; ++range) {
for (i = 1; i + range <= n; ++i) qry(i,i+range);
}
vector<int> edge[101];
queue<int> q;
int ind[101] = { 0 };
for (i = 1; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
if (mat[i][j]) {
edge[i].push_back(j);
++ind[j];
}
}
}
int src = 1; while (ind[src]) ++src;
q.push(src);
for (int i = src + 1; i <= n; ++i) {
if (ind[i] == 0) {
edge[src].push_back(i);
++ind[i];
src = i;
}
}
//tp_sort(q,s,ind,edge);
i = 1;
dfs(q.front(), i, s, edge); q.pop();
for (i = 1; i <= n; ++i) ind[i] = 0;
for (i = 1; i <= n; ++i) {
edge[i].clear();
for (int j = i+1; j <= n; ++j) {
if (mat[i][j]) {
edge[i].push_back(j);
++ind[j];
}
}
}
src = n; while (ind[src]) --src;
q.push(src);
for (int i = src -1; i >0; --i) {
if (ind[i] == 0) {
edge[src].push_back(i);
++ind[i];
src = i;
}
}
//tp_sort(q, l, ind, edge);
i = 1;
dfs(q.front(), i, l, edge);
for (printf("end\n"), i = 1; i <= n; ++i) printf("%d ",s[i]);
for (printf("\n"), i = 1; i <= n; ++i) printf("%d ", l[i]);
fflush(stdout);
return 0;
}
Compilation message
zagonetka.cpp: In function 'void qry(int, int)':
zagonetka.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < loc.size(); ++i) {
~~^~~~~~~~~~~~
zagonetka.cpp:43:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = i + 1; j < loc.size(); ++j) {
~~^~~~~~~~~~~~
zagonetka.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&i);
~~~~~^~~~~~~~~
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:70:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (scanf("%d", &n), i = 1; i <= n; ++i) {
~~~~~~~~~~~~~~~^~~~~~~
zagonetka.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", p + i);
~~~~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
396 KB |
Output is correct |
| 2 |
Incorrect |
36 ms |
316 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
99 ms |
316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
