제출 #640864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
640864		anhduc2701	Zagonetka (COI18_zagonetka)	C++17	100 / 100	125 ms	472 KiB

zagonetka

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
int n;
int pos[105];
int a[105];
int ray[105];
int ok[105][105];
int den[105];
int mang[105];
vector<int> G[105];
void print()
{
    for (int i = 1; i <= n; i++)
    {
        ray[i] = i;
        den[i] = 0;
        G[i].clear();
    }
    priority_queue<int> pq;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            if (ok[i][j])
            {
                G[pos[j]].push_back(pos[i]);
                den[pos[i]]++;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (den[i] == 0)
        {
            pq.push(i);
        }
    }
    int luot = n + 1;
    while (pq.size())
    {
        int z = pq.top();
        pq.pop();
        mang[z] = --luot;
        for (auto v : G[z])
        {
            den[v]--;
            if (!den[v])
                pq.push(v);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cout << mang[i] << ' ';
    }
    cout << endl;
}
void print2()
{
    for (int i = 1; i <= n; i++)
    {
        ray[i] = i;
        den[i] = 0;
        G[i].clear();
    }
    priority_queue<int> pq;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            if (ok[i][j])
            {
                G[pos[i]].push_back(pos[j]);
                den[pos[j]]++;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (den[i] == 0)
        {
            pq.push(i);
        }
    }
    int luot = 0;
    while (pq.size())
    {
        int z = pq.top();
        pq.pop();
        mang[z] = ++luot;
        for (auto v : G[z])
        {
            den[v]--;
            if (!den[v])
                pq.push(v);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cout << mang[i] << ' ';
    }
}
signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pos[a[i]] = i;
    }
    for (int len = 1; len <= n; len++)
    {
        for (int l = 1; l <= n - len; l++)
        {
            int r = l + len;
            for (int i = 1; i <= n; i++)
            {
                ray[i] = i;
                den[i] = 0;
                G[i].clear();
            }
            for (int i = l; i <= r; i++)
            {
                ray[i] = 0;
            }
            for (int i = l; i <= r; i++)
            {
                for (int j = i + 1; j <= r; j++)
                {
                    if (ok[i][j])
                    {
                        G[j].push_back(i);
                        den[i]++;
                    }
                }
            }
            G[l].push_back(r);
            den[r]++;
            queue<int> topo;
            int luot = r + 1;
            for (int i = l; i <= r; i++)
            {
                if (!den[i])topo.push(i);
            }
            while (topo.size())
            {
                int z = topo.front();
                topo.pop();
                ray[z] = --luot;
                for (auto v : G[z])
                {
                    den[v]--;
                    if (!den[v])
                        topo.push(v);
                }
            }
            int check = 0;
            for (int i = 1; i <= n; i++)
            {
                if (!ray[i])
                    check = 1;
            }
            if (check == 1)
            {
                ok[l][r] = 1;
                continue;
            }
            for (int i = 1; i <= n; i++)
            {
                mang[pos[i]] = ray[i];
            }
            cout << "query ";
            for (int i = 1; i <= n; i++)
            {
                cout << mang[i] << ' ';
            }
            cout << endl;
            int x;
            cin >> x;
            if (!x)
                ok[l][r] = 1;
        }
    }
    cout << "end " << endl;
    print();
    print2();
}

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