oj.uz

Submission #640772

# Submission time Handle Problem Language Result Execution time Memory
640772 2022-09-15T08:05:05 Z Tuanlinh123 Zagonetka (COI18_zagonetka) C++17
0 / 100
 78 ms 324 KB 
#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;
}

priority_queue <ll> p1;

void solve_max()
{
    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])
            p1.push(i);
    while (!p1.empty())
    {
        ll x=p1.top(); p1.pop();
//        cout << x << " ";
        ans[x]=++Time;
        for (ll i=0; i<A[x].size(); i++)
        {
            ll v=A[x][i];
            if (used[v])
                continue;
            p1.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

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:149: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]
  149 |         for (ll i=0; i<A[x].size(); i++)
      |                      ~^~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 324 KB Output isn't correct
2 Halted 0 ms 0 KB -