Submission #944039

#TimeUsernameProblemLanguageResultExecution timeMemory
944039thunoproChameleon's Love (JOI20_chameleon)C++14
100 / 100
50 ms616 KiB
#include<bits/stdc++.h> using namespace std ; #define maxn 200009 #define ll long long #define pb push_back #define fi first #define se second #define left id<<1 #define right id<<1|1 #define re exit(0); #define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1 #define TIME ( 1.0*clock() / CLOCKS_PER_SEC ) const int mod = 1e9+7 ; const int INF = 1e9 ; typedef vector<int> vi ; typedef pair<int,int> pii ; typedef vector<pii> vii ; template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; } template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; } void add ( int &a , int b ) { a += b ; if ( a >= mod ) a -= mod ; if ( a < 0 ) a += mod ; } void rf () { freopen ("bai1.inp","r",stdin) ; } mt19937 rng (time(0)) ; int _pow ( int a , int n ) { if ( n == 0 ) return 1 ; int res = _pow (a,n/2) ; if ( n % 2 ) return 1ll*res*res%mod*a%mod ; else return 1ll*res*res%mod ; } #include "chameleon.h" bool bad ( vi v , int x ) { v . pb (x) ; return Query (v) != v.size () ; } void Solve ( int n ) { vi adj [2*n+5] ; for ( int cr = 1 ; cr <= 2*n ; cr ++ ) { vi colour (cr) , inset [2] ; function<void(int,int)> dfs = [&] ( int nw , int cl ) { if ( colour [nw] ) return ; colour [nw] = cl ; for ( auto nx : adj [nw] ) dfs (nx,3-cl) ; }; for ( int i = 1 ; i < cr ; i ++ ) { if ( !colour [i] ) dfs (i,1) ; inset [colour[i]-1] . pb (i) ; } for ( int i = 0 ; i < 2 ; i ++ ) { while ( bad(inset[i],cr) ) { int lf = 1 , rg = inset[i].size () ; for ( int md ; lf < rg ; ) { md = (lf+rg)/2 ; if ( bad(vi(inset[i].begin(),inset[i].begin()+md),cr)) rg = md ; else lf = md+1 ; } adj [cr] . pb (inset[i][lf-1]) ; adj [inset[i][lf-1]] . pb (cr) ; inset [i] = vi (inset[i].begin()+lf,inset[i].end()) ; } } } vi same (2*n+5) , n1 (2*n+5) , n2 (2*n+5) ; for ( int i = 1 ; i <= 2*n ; i ++ ) { if ( adj [i].size () == 1 ) same [i] = adj [i][0] ; else { while ( Query ({i,adj[i][0],adj[i][1]}) != 1 ) { rotate (adj[i].begin(),adj[i].begin()+1,adj[i].end()) ; } n1 [i] = adj [i][2] ; n2 [adj[i][2]] = i ; } } for ( int i = 1 ; i <= 2*n ; i ++ ) { if ( !same[i] ) { same [i] = adj [i][0] + adj [i][1] + adj [i][2] - n1 [i] - n2 [i] ; } if ( i > same [i] ) Answer (same[i],i) ; } return ; } //int main () //{ // ios_base::sync_with_stdio(0); // cin.tie(0);cout.tie(0); //// rf () ; // //}

Compilation message (stderr)

chameleon.cpp: In function 'bool bad(vi, int)':
chameleon.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  return Query (v) != v.size () ;
      |         ~~~~~~~~~~^~~~~~~~~~~~
chameleon.cpp: In function 'void rf()':
chameleon.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...