Submission #640746

#	Time	Username	Problem	Language	Result	Execution time	Memory
640746		Tuanlinh123	Zagonetka (COI18_zagonetka)	C++17	0 / 100	74 ms	332 KiB

zagonetka

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

#define LOCALIO "C:/Users/admin/Documents/Code/freopen/"

ll a[105], a1[105], p[105], deg[105], n, Time;
bool check[105][105];
ll used[105], ans[105];
vector <ll> A[105];

ll query()
{
    cout << "query ";
    for (ll i=1; i<=n; i++)
        cout << a1[i] << " ";
    cout << endl;
    ll x; cin >> x;
    return x;
}

bool build(ll u)
{
    used[u]=2;
    for (ll i=0; i<A[u].size(); i++)
    {
        ll v=A[u][i];
        if (used[v]==2)
            return 0;
        if (!used[v])
        {
            bool c=build(v);
            if (c==0) return 0;
        }
    }
    p[u]=++Time;
    used[u]=1;
    return 1;
}

void solve(ll l, ll r)
{
//    cout << l << " " << r << " bru\n";
    Time=-1;
    for (ll i=l; i<=r; i++)
        A[i].clear(), used[i]=0;
    for (ll i=l; i<=r; i++)
        for (ll j=l; j<=r; j++)
            if (check[i][j])
                A[j].pb(i);
    if (a[l]<a[r])
        A[l].pb(r);
    else A[r].pb(l);
//    for (ll i=l; i<=r; i++)
//        for (ll j=0; j<A[i].size(); i++)
//            cout << i << " " << A[i][j] << "\n";
    for (ll i=l; i<=r; i++)
    {
        if (!used[i])
        {
            ll x=build(i);
            if (x==0)
            {
//                cout << i << "\n";
                if (a[l]<a[r])
                    check[l][r]=1;
                else check[r][l]=1;
                return;
            }
        }
    }
    vector <ll> num;
    for (ll i=l; i<=r; i++)
        num.pb(a[i]);
    sort(num.begin(), num.end());
    for (ll i=1; i<=n; i++)
        a1[i]=a[i];
    for (ll i=l; i<=r; i++)
        a1[i]=num[p[i]];
    ll x=query();
    if (x==0)
    {
        if (a[l]<a[r])
            check[l][r]=1;
        else check[r][l]=1;
        return;
    }
}

priority_queue <ll, vector <ll>, greater <ll>> q;

void solve_min()
{
    Time=0;
    for (ll i=1; i<=n; i++)
        A[i].clear(), deg[i]=0, used[i]=0;
    for (ll i=1; i<=n; i++)
        for (ll j=1; j<=n; j++)
            if (check[i][j])
                A[i].pb(j), deg[j]++;
    for (ll i=1; i<=n; i++)
        if (!deg[i])
            q.push(i);
    while (!q.empty())
    {
        ll x=q.top(); q.pop();
//        cout << x << " ";
        ans[x]=++Time;
        for (ll i=0; i<A[x].size(); i++)
        {
            ll v=A[x][i];
            if (used[v])
                continue;
            q.push(v); used[v]=1;
        }
    }
//    cout << "\n";
    for (ll i=1; i<=n; i++)
        cout << ans[i] << " ";
    cout << endl;
}

void solve_max()
{
    Time=n;
    for (ll i=1; i<=n; i++)
        A[i].clear(), deg[i]=0, used[i]=0;
    for (ll i=1; i<=n; i++)
        for (ll j=1; j<=n; j++)
            if (check[i][j])
                A[j].pb(i), deg[i]++;
    for (ll i=1; i<=n; i++)
        if (!deg[i])
            q.push(i);
    while (!q.empty())
    {
        ll x=q.top(); q.pop();
//        cout << x << " ";
        ans[x]=Time--;
        for (ll i=0; i<A[x].size(); i++)
        {
            ll v=A[x][i];
            if (used[v])
                continue;
            q.push(v); used[v]=1;
        }
    }
//    cout << "\n";
    for (ll i=1; i<=n; i++)
        cout << ans[i] << " ";
    cout << endl;
}

int main()
{
    #ifdef LOCAL
        freopen( LOCALIO "input.txt","r",stdin) ;
        freopen( LOCALIO "output.txt","w",stdout) ;
    #endif

    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
//	freopen("FIBONACCI.inp","r",stdin);
//	freopen("FIBONACCI.out","w",stdout);
    cin >> n;
    for (ll i=1; i<=n; i++)
        cin >> a[i];
    for (ll i=1; i<=n; i++)
        for (ll j=i-1; j>=1; j--)
            solve(j, i);
    cout << "end" << endl;
//    for (ll i=1; i<=n; i++)
//        for (ll j=1; j<=n; j++)
//            cout << i << " " << j << " " << check[i][j] << "\n";
    solve_min(); solve_max();
}

Compilation message (stderr)

zagonetka.cpp: In function 'bool build(long long int)':
zagonetka.cpp:32:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (ll i=0; i<A[u].size(); i++)
      |                  ~^~~~~~~~~~~~
zagonetka.cpp: In function 'void solve_min()':
zagonetka.cpp:116:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for (ll i=0; i<A[x].size(); i++)
      |                      ~^~~~~~~~~~~~
zagonetka.cpp: In function 'void solve_max()':
zagonetka.cpp:147:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         for (ll i=0; i<A[x].size(); i++)
      |                      ~^~~~~~~~~~~~

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