Submission #640687

#	Time	Username	Problem	Language	Result	Execution time	Memory
640687		Hiennoob123	Zagonetka (COI18_zagonetka)	C++14	100 / 100	105 ms	468 KiB

zagonetka

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define ld double
#define cd complex<ld>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std ;
ll A[105] ;
ll pos[105] ;
ll cnt1[105] ;
ll cnt2[105] ;
vector<pll> edge ;
bool inv[100005] = {} ;
ll check[105] = {} ;
vector<ll> T[105] ;
ll low = 0 , up = 0 ;
vector<ll> topo , topo1 , topo2 ;
ll used[105] ;
vector<ll> T1[105] , T2[105] ;
ll val1[105] , val2[105] ;
bool wrong = 0 ;
void dfs(ll v , ll root)
{
    if(check[v]==root)
    {
        wrong = 1 ;
        return ;
    }
    else if(check[v]!=0) return ;
    if(A[v]<low||A[v]>up) return ;
    check[v] = root ;
    //cout << v << "\n" ;
    for(int i = 0 ; i< T[v].size() ; i++)
    {
        ll idx = T[v][i] ;
        if(inv[idx])
        {
            if(edge[idx].se==v)
            {
                dfs(edge[idx].fi , root) ;
            }
        }
        else
        {
            if(edge[idx].fi==v)
            {
                dfs(edge[idx].se , root) ;
            }
        }
    }
    topo.push_back(v) ;
}
void dfsk1(ll v , ll le)
{
    if(check[v])
    {
        return ;
    }
    else
    {
        check[v] = 1 ;
        val1[v] = 1 ;
        for(int i = 0 ; i < T1[v].size() ; i++)
        {
            dfsk1(T1[v][i] , le) ;
            val1[v] = max(val1[v] , val1[T1[v][i]]+1) ;
        }
        topo1.push_back(v) ;
    }
}
void dfsk2(ll v , ll le)
{
    if(check[v])
    {
        return ;
    }
    else
    {
        check[v] = 1 ;
        val2[v] = 1 ;
        for(int i = 0 ; i < T2[v].size() ; i++)
        {
            dfsk2(T2[v][i] , le) ;
            val2[v] = max(val2[v] , val2[T2[v][i]]+1) ;
        }
        //cout << v << "\n" ;
        topo2.push_back(v) ;
    }
}
void solve()
{
    ll n ;
    cin >> n ;
    //assert(n==2) ;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> A[i] ;
        pos[A[i]] = i ;
    }
    //assert(n==3) ;
    for(int i = 1 ; i < n ; i++)
    {
        for(int j = 1 ; j<= n-i ; j++)
        {
            //if(i!=1) break ;
            //cout << i+j << " " << i << " " << pos[i+j] << " " << pos[i] << "\n" ;
            //cout << j << " " << i +j << "\n" ;
            wrong = 0 ;
            for(int k = 1 ; k<= n ; k++)
            {
                check[k] = 0 ;
            }
            edge.push_back({pos[i+j] , pos[j]}) ;
            inv[edge.size()-1] = 1 ;
            topo.clear() ;
            T[pos[i+j]].push_back(edge.size()-1) ;
            T[pos[j]].push_back(edge.size()-1) ;
            low = j ; up = i+j ;
            for(int k = low ; k<= up ; k++)
            {
                //cout << pos[k] << "-1\n" ;
                dfs(pos[k] , pos[k]) ;
            }
            //assert(n==3) ;
            assert(up-low+1==topo.size()) ;
            for(int k = 1 ; k<= n ; k++) used[k] = A[k] ;
            for(int k = low ; k<= up ; k++)
            {
                //cout << k-low << " " << topo[k-low] << " " << k << "\n" ;
                used[topo[topo.size()-1-(k-low)]] = up+low-k ;
            }
            cout << "query " ;
            for(int k = 1 ; k<= n ; k++) cout << used[k] << " " ;
            cout << endl ;
            int f = 0 ;
            cin >> f ;
            if(f==0&&!wrong)
            {
                //cout << pos[i+j] << " " << pos[j] << "\n" ;
                inv[edge.size()-1] = 0 ;
            }
            else
            {
                //assert(n==3) ;
                edge.pop_back() ;
                T[pos[i+j]].pop_back() ;
                T[pos[j]].pop_back() ;
                //assert(n==3) ;
            }
        }
    }
    //assert(n==3) ;
    for(int i = 0 ; i< edge.size() ; i++)
    {
        T1[edge[i].fi].push_back(edge[i].se) ;
        T2[edge[i].se].push_back(edge[i].fi) ;
        cnt1[edge[i].fi]++ ;
        cnt2[edge[i].se]++ ;
        //cout << edge[i].fi << " " << edge[i].se << '\n' ;
    }
    priority_queue<ll> q1 ;
    priority_queue<ll> q ;
    for(int i = 1 ; i<= n ; i++)
    {
        if(cnt2[i]==0) q.push(i) ;
    }
    ll ti = 0 ;
    while(!q.empty())
    {
        ll x = q.top() ;
        q.pop() ;
        ti++ ;
        val1[x] = ti ;
        for(int i = 0 ; i< T1[x].size() ; i++)
        {
            cnt2[T1[x][i]]-- ;
            if(cnt2[T1[x][i]]==0)
            {
                q.push(T1[x][i]) ;
            }
        }
    }
    for(int i = 1 ; i<= n ; i++)
    {
        if(cnt1[i]==0) q1.push(i) ;
    }
    ti = 0 ;
    while(!q1.empty())
    {
        ll x = q1.top() ;
        q1.pop() ;
        ti++ ;
        val2[x] = ti ;
        //cout << x << "\n" ;
        for(int i = 0 ; i< T2[x].size() ; i++)
        {
            cnt1[T2[x][i]]-- ;
            if(cnt1[T2[x][i]]==0)
            {
                q1.push(T2[x][i]) ;
            }
        }
    }
    //for(int i = 0 ; i< n ; i++) cout << topo1[i] << " " ;
    //cout << "\n" ;
    //for(int i = 0 ; i< n ; i++) cout << topo2[i] << " " ;
    //for(int i = 0 ; i< n ; i++) save1[topo1[i]] = i ;
    //for(int j = 0 ; j< n ; j++) save2[topo1[j]] = i ;
    //for(int i = 0 ; i< n; i ++) val1[topo1[i]] = i+1 ;
    //for(int i = 0 ; i< n ; i++) val2[topo2[i]] = n-i;
    cout << "end" << endl ;
    for(int i = 1 ; i<= n ; i++) cout << n+1-val1[i] << " " ;
    cout << endl ;
    for(int j = 1 ; j<= n ; j++) cout << val2[j] << " " ;
    cout << endl ;

}
signed main()
{
    //ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
    //freopen("IN.txt","r",stdin) ;
    //freopen("LINES.inp" , "r" , stdin) ;
    //freopen("LINES.out" , "w" , stdout) ;
    //freopen("OUT.txt" , "w" , stdout) ;
    int t = 1 ;
    //cout << t << " " << n << "\n" ;
    for(int i = 1 ; i<= t ; i++)
    {
        solve();
    }
}

Compilation message (stderr)

zagonetka.cpp: In function 'void dfs(long long int, long long int)':
zagonetka.cpp:38:22: 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]
   38 |     for(int i = 0 ; i< T[v].size() ; i++)
      |                     ~^~~~~~~~~~~~~
zagonetka.cpp: In function 'void dfsk1(long long int, long long int)':
zagonetka.cpp:68:27: 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]
   68 |         for(int i = 0 ; i < T1[v].size() ; i++)
      |                         ~~^~~~~~~~~~~~~~
zagonetka.cpp: In function 'void dfsk2(long long int, long long int)':
zagonetka.cpp:86:27: 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]
   86 |         for(int i = 0 ; i < T2[v].size() ; i++)
      |                         ~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from zagonetka.cpp:1:
zagonetka.cpp: In function 'void solve()':
zagonetka.cpp:130:28: 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]
  130 |             assert(up-low+1==topo.size()) ;
      |                    ~~~~~~~~^~~~~~~~~~~~~
zagonetka.cpp:158:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     for(int i = 0 ; i< edge.size() ; i++)
      |                     ~^~~~~~~~~~~~~
zagonetka.cpp:179:26: 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]
  179 |         for(int i = 0 ; i< T1[x].size() ; i++)
      |                         ~^~~~~~~~~~~~~~
zagonetka.cpp:200:26: 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]
  200 |         for(int i = 0 ; i< T2[x].size() ; i++)
      |                         ~^~~~~~~~~~~~~~

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