제출 #1223450

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223450		12345678	Zagonetka (COI18_zagonetka)	C++20	49 / 100	3070 ms	428 KiB

zagonetka

#include <bits/stdc++.h>

using namespace std;

const int nx=105;

int n, p[nx], idx[nx], c[nx], vs[nx], deg[nx], tmp[nx], x, t, mn[nx], mx[nx];
vector<int> d[nx], g[nx], rv[nx];
queue<int> q;
priority_queue<int> pq;

void dfs(int u)
{
    vs[u]=1;
    for (auto v:d[u]) dfs(v);
}

int main() {
    cin>>n;
    for (int i=1; i<=n; i++) cin>>p[i], idx[p[i]]=i;
    for (int g=1; g<n; g++)
    {
        for (int l=1; l+g<=n; l++)
        {
            int r=l+g, cur=l;
            for (int i=1; i<=n; i++) vs[i]=0, deg[i]=0;
            dfs(l);
            if (vs[r]) continue;
            d[r].push_back(l);
            for (int i=l; i<=r; i++) for (auto v:d[i]) if (v<=r) deg[v]++;
            for (int i=l; i<=r; i++) if (!deg[i]) q.push(i);
            for (int i=1; i<=n; i++) c[i]=i;
            while (!q.empty())
            {
                auto u=q.front();
                q.pop();
                c[u]=cur++;
                for (auto v:d[u]) if (v<=r&&!--deg[v]) q.push(v);
            }
            d[r].pop_back();
            cout<<"query ";
            for (int i=1; i<=n; i++) cout<<c[p[i]]<<' ';
            cout<<endl;
            cin>>x;
            if (!x) d[l].push_back(r); //cout<<"edge "<<l<<' '<<r<<endl;
        }
    }
    for (int i=1; i<=n; i++) deg[i]=0;
    for (int i=1; i<=n; i++) for (auto v:d[i]) rv[idx[v]].push_back(idx[i]), deg[idx[i]]++;
    for (int i=1; i<=n; i++) if (!deg[i]) pq.push(i);
    t=n;
    while (!pq.empty())
    {
        auto u=pq.top();
        pq.pop();
        mn[u]=t--;
        for (auto v:rv[u]) if (!--deg[v]) pq.push(v);
    }
    for (int i=1; i<=n; i++) deg[i]=0;
    for (int i=1; i<=n; i++) for (auto v:d[i]) g[idx[i]].push_back(idx[v]), deg[idx[v]]++;
    for (int i=1; i<=n; i++) if (!deg[i]) pq.push(i);
    while (!pq.empty())
    {
        auto u=pq.top();
        pq.pop();
        mx[u]=++t;
        for (auto v:g[u]) if (!--deg[v]) pq.push(v);
    }
    cout<<"end"<<endl;
    for (int i=1;i <=n; i++) cout<<mn[i]<<' ';
    cout<<endl;
    for (int i=1; i<=n; i++) cout<<mx[i]<<' ';
    cout<<endl;
}

• Subtask 1: 9 / 9
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 0 / 51