oj.uz

Submission #230242

# Submission time Handle Problem Language Result Execution time Memory
230242 2020-05-09T11:14:28 Z Arg_007 Mouse (info1cup19_mouse) C++14
100 / 100
 100 ms 504 KB 
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define mp make_pair
#define PI ( acos(-1.0) )
#define IN freopen("hard1.txt","r",stdin)
#define OUT freopen("hard1.txt","w",stdout)
#define FOR(i,a,b) for(i=a ; i<=b ; i++)
#define DBG printf("Hi\n")
#define i64 long long int
#define eps (1e-8)
#define xx first
#define yy second
#define ln 17
#define off 1000005
#define FastIO  ios_base::sync_with_stdio(false); cin.tie(NULL)


using namespace __gnu_pbds;
using namespace std ;

typedef tree< i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef pair<i64, i64> pii ;

#define maxn 1000005
#define mod 1000000007LL
#define lim 1000000000
#define INF 4500000000000000000LL

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


#include <grader.h>

/*
vector <int> myPerm ;
int query( vector <int> vec )
{
    int mat = 0 ;
    for(int i=0 ; i<vec.size() ; i++)
    {
        if( vec[i]==myPerm[i] ) mat++ ;
    }
    return mat ;
}
*/
int ask( vector <int> vec )
{
    int N = (int)vec.size() ;
    for(int i=0 ; i<N ; i++) vec[i]++ ;
    return query(vec) ;
}

int askWithDoubt( vector <int> perm , vector < pair<int,int> > doubt )
{
    for(int i=0 ; i<doubt.size() ; i++)
    {
        swap( perm[ doubt[i].xx ] , perm[ doubt[i].yy ] ) ;
    }
    int mat = ask(perm) ;
    return mat ;
}

pair<int,int> recur( vector <int> perm , vector < pair<int,int> > doubt )
{
    if( doubt.size() == 1 ) return doubt[0] ;
    int m = (doubt.size())/2 ;

    vector < pair<int,int> > d1 , d2 ;

    for(int i=0 ; i<m ; i++) d1.pb(doubt[i]) ;
    for(int i=m ; i<doubt.size() ; i++) d2.pb( doubt[i] ) ;

    int mat = askWithDoubt(perm,d1) ;

    if(mat) return recur(perm,d1) ;
    else return recur(perm,d2) ;
}

int vis[305] ;
vector <int> g[305] ;

void solve(int N)
{
 //   DBG ;
    vector <int> perm ;
    for(int i=0 ; i<N ; i++) perm.pb(i) ;

    while( 1 )
    {
        if( ask(perm) == 0 ) break ;
        shuffle( perm.begin() , perm.end() , rng ) ;
    }

 //   for(int i=0 ; i<perm.size() ; i++) printf("%d ",perm[i]+1) ;
 //   printf("\n") ;

    int M = N ;
    if(M%2 == 0 ) M-- ;

    vector < pair<int,int> > realPairs ;

    for(int i=0 ; i<M ; i++)
    {
        vector < pair<int,int> > doubt ;
        for(int j=0 ; j<M ; j++)
        {
            if(i==j) continue ;
        //    printf("-- %d %d\n" , i , j ) ;
            int x = j, y = (( 2*i - x)%M + M)%M ;
        //    printf("%d %d\n",y,M) ;
            if(y<x) continue ;
            doubt.pb(  mp(x,y) ) ;
        }
        if( N!=M ) doubt.pb( mp(i,M) ) ;

  //      for( auto d: doubt) printf("%d %d\n",d.xx,d.yy) ;
  //      printf("\n\n") ;

        while( doubt.size() > 0 &&  askWithDoubt(perm,doubt) > 0 )
        {
            pair<int,int> p = recur(perm,doubt) ;
            realPairs.pb(p) ;
            for(int i=0 ; i<doubt.size() ; i++)
            {
                if( doubt[i]==p )
                {
                    doubt.erase(doubt.begin()+i) ;
                    break ;
                }
            }
        }
    }

    for(int i=0 ; i<N ; i++) g[i].clear() ;

    for(int i=0 ; i<realPairs.size() ; i++)
    {
        int u = realPairs[i].xx , v = realPairs[i].yy ;
        g[ u ].pb(v) ; g[v].pb(u) ;
    }

  //  for(int i=0 ; i<realPairs.size() ; i++) printf("%d %d\n",realPairs[i].xx,realPairs[i].yy) ;

    vector <int> ans(N,0) ;
    memset(vis,0,sizeof(vis)) ;

    for(int i=0 ; i<N ; i++)
    {
        if(vis[i]) continue ;
        vector <int> vec ;
        int cur = i ;

        if( g[cur].size()==1 || g[cur][0] == g[cur][1] )
        {
            int u = cur , v = g[cur][0] ;
            vis[u] = 1 ; vis[v] = 1 ;
            ans[u] = perm[v] ; ans[v] = perm[u] ;
            continue ;
        }

        vis[cur] = 1 ;
        vec.pb(cur) ;

        int prev = cur ;
        vec.pb(cur) ;
        cur = g[cur][0] ;
        while( !vis[cur] )
        {
            vec.pb(cur) ;
            vis[cur] = 1 ;
            int nCur = (g[cur][0]^g[cur][1]^prev) ;
            prev = cur ;
            cur = nCur ;
        }

        vector <int> nPerm = perm ;

        int temp = nPerm[ vec[0] ] ;
        for(int i=1 ; i<vec.size() ; i++)
        {
            nPerm[ vec[i-1] ] = nPerm[ vec[i] ] ;
        }
        nPerm[ vec.back() ] = temp ;

        int mat = ask(nPerm) ;
        if(mat > 0)
        {
            for(int i=0 ; i<vec.size() ; i++)
            {
                ans[ vec[i] ] = nPerm[vec[i] ] ;
            }
        }
        else{
            for(int i=1 ; i<vec.size() ; i++) ans[ vec[i] ] = perm[ vec[i-1] ] ;
            ans[ vec[0] ] = perm[ vec.back() ] ;
        }
    }
    /*
    for(int i=0 ; i<ans.size() ; i++) printf("%d ",ans[i]+1) ;
    printf("\n") ; */

    ask(ans) ;
}
/*
int main()
{
    myPerm = { 3 , 1 , 5 , 2 , 7 , 4 , 6 } ;

    solve(7) ;

    return 0 ;
}
*/

Compilation message

mouse.cpp: In function 'int askWithDoubt(std::vector<int>, std::vector<std::pair<int, int> >)':
mouse.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0 ; i<doubt.size() ; i++)
                   ~^~~~~~~~~~~~~
mouse.cpp: In function 'std::pair<int, int> recur(std::vector<int>, std::vector<std::pair<int, int> >)':
mouse.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=m ; i<doubt.size() ; i++) d2.pb( doubt[i] ) ;
                   ~^~~~~~~~~~~~~
mouse.cpp: In function 'void solve(int)':
mouse.cpp:127:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0 ; i<doubt.size() ; i++)
                           ~^~~~~~~~~~~~~
mouse.cpp:140:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0 ; i<realPairs.size() ; i++)
                   ~^~~~~~~~~~~~~~~~~
mouse.cpp:183:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=1 ; i<vec.size() ; i++)
                       ~^~~~~~~~~~~
mouse.cpp:192:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0 ; i<vec.size() ; i++)
                           ~^~~~~~~~~~~
mouse.cpp:198:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=1 ; i<vec.size() ; i++) ans[ vec[i] ] = perm[ vec[i-1] ] ;
                           ~^~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Correct! Number of queries: 26
2 Correct 5 ms 384 KB Correct! Number of queries: 10
3 Correct 5 ms 384 KB Correct! Number of queries: 20
4 Correct 5 ms 384 KB Correct! Number of queries: 23
5 Correct 5 ms 384 KB Correct! Number of queries: 22
6 Correct 5 ms 384 KB Correct! Number of queries: 24

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Correct! Number of queries: 26
2 Correct 5 ms 384 KB Correct! Number of queries: 10
3 Correct 5 ms 384 KB Correct! Number of queries: 20
4 Correct 5 ms 384 KB Correct! Number of queries: 23
5 Correct 5 ms 384 KB Correct! Number of queries: 22
6 Correct 5 ms 384 KB Correct! Number of queries: 24
7 Correct 10 ms 384 KB Correct! Number of queries: 400
8 Correct 9 ms 384 KB Correct! Number of queries: 400
9 Correct 9 ms 384 KB Correct! Number of queries: 400
10 Correct 10 ms 384 KB Correct! Number of queries: 400
11 Correct 9 ms 384 KB Correct! Number of queries: 300
12 Correct 10 ms 384 KB Correct! Number of queries: 400
13 Correct 10 ms 384 KB Correct! Number of queries: 400
14 Correct 11 ms 384 KB Correct! Number of queries: 400
15 Correct 11 ms 384 KB Correct! Number of queries: 400
16 Correct 10 ms 384 KB Correct! Number of queries: 400

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Correct! Number of queries: 26
2 Correct 5 ms 384 KB Correct! Number of queries: 10
3 Correct 5 ms 384 KB Correct! Number of queries: 20
4 Correct 5 ms 384 KB Correct! Number of queries: 23
5 Correct 5 ms 384 KB Correct! Number of queries: 22
6 Correct 5 ms 384 KB Correct! Number of queries: 24
7 Correct 10 ms 384 KB Correct! Number of queries: 400
8 Correct 9 ms 384 KB Correct! Number of queries: 400
9 Correct 9 ms 384 KB Correct! Number of queries: 400
10 Correct 10 ms 384 KB Correct! Number of queries: 400
11 Correct 9 ms 384 KB Correct! Number of queries: 300
12 Correct 10 ms 384 KB Correct! Number of queries: 400
13 Correct 10 ms 384 KB Correct! Number of queries: 400
14 Correct 11 ms 384 KB Correct! Number of queries: 400
15 Correct 11 ms 384 KB Correct! Number of queries: 400
16 Correct 10 ms 384 KB Correct! Number of queries: 400
17 Correct 82 ms 384 KB Correct! Number of queries: 2400
18 Correct 76 ms 504 KB Correct! Number of queries: 2200
19 Correct 77 ms 384 KB Correct! Number of queries: 2200
20 Correct 82 ms 384 KB Correct! Number of queries: 2400
21 Correct 84 ms 384 KB Correct! Number of queries: 2300
22 Correct 74 ms 384 KB Correct! Number of queries: 2200
23 Correct 82 ms 384 KB Correct! Number of queries: 2300
24 Correct 100 ms 384 KB Correct! Number of queries: 2400
25 Correct 77 ms 384 KB Correct! Number of queries: 2400
26 Correct 93 ms 384 KB Correct! Number of queries: 2400