Submission #640614

#	Time	Username	Problem	Language	Result	Execution time	Memory
640614		Hiennoob123	Zagonetka (COI18_zagonetka)	C++14	0 / 100	1 ms	464 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] ;
vector<pll> edge ;
bool inv[100005] = {} ;
bool 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] ;
void dfs(ll v)
{
    if(check[v]) return ;
    if(A[v]<low||A[v]>up) return ;
    check[v] = 1 ;
    //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) ;
            }
        }
        else
        {
            if(edge[idx].fi==v)
            {
                dfs(edge[idx].se) ;
            }
        }
    }
    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) ;
        }
        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" ;
            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]) ;
            }
            assert(n==3) ;
            for(int k = 1 ; k<= n ; k++) used[k] = pos[k] ;
            for(int k = low ; k<= up ; k++)
            {
                //cout << k-low << "\n" ;
                used[topo[k-low]] = k ;
            }
            cout << "query " ;
            for(int k = 1 ; k<= n ; k++) cout << used[k] << " " ;
            cout << endl ;
            int f = 0 ;
            cin >> f ;
            if(f==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) ;
    }
    //for(int i = 0 ; i< edge.size() ; i++) cout << edge[i].fi << " " << edge[i].se << "\n" ;
    for(int j = 1 ; j<= n ; j++) check[j] = 0 ;
    for(int i = 1 ; i<= n ; i++)
    {
        dfsk1(i , 0) ;
    }
    for(int j = 1 ; j<= n ; j++) check[j] = 0 ;
    for(int i = 1 ; i<= n ; i++)
    {
        dfsk2(i , 0) ;
    }
    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 << 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)':
zagonetka.cpp:30: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]
   30 |     for(int i = 0 ; i< T[v].size() ; i++)
      |                     ~^~~~~~~~~~~~~
zagonetka.cpp: In function 'void dfsk1(long long int, long long int)':
zagonetka.cpp:60: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]
   60 |         for(int i = 0 ; i < T1[v].size() ; i++)
      |                         ~~^~~~~~~~~~~~~~
zagonetka.cpp: In function 'void dfsk2(long long int, long long int)':
zagonetka.cpp:78: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]
   78 |         for(int i = 0 ; i < T2[v].size() ; i++)
      |                         ~~^~~~~~~~~~~~~~
zagonetka.cpp: In function 'void solve()':
zagonetka.cpp:145: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]
  145 |     for(int i = 0 ; i< edge.size() ; i++)
      |                     ~^~~~~~~~~~~~~

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