Submission #959092

#	Time	Username	Problem	Language	Result	Execution time	Memory
959092		lollipop	The Collection Game (BOI21_swaps)	C++17	35 / 100	37 ms	1744 KiB

swaps

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class T> using ordered_set =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int N = 2e5 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;

#include "swaps.h"


vector < vector < pair < int , int > > > dd ;
vector < int > ans ; 

vector < pair < int , int > > lst , nxt ;

void build(){
	dd.pb( lst ) ;
    int tt = 0 ; 
	for( auto x : lst ){
		if( x.f != x.s ) tt = 1 ; 
	}
	if( tt == 0 ) return ; 
	for( auto x : lst ){
		if( x.f == x.s ) nxt.pb( x ) ;
		else{
			int l = x.f , r = x.s ;
			int mid = ( l + r ) / 2 ;
			nxt.pb( { l , mid } ) ;
			nxt.pb( { mid + 1 , r } ) ;
		}
	}
	lst = nxt ; nxt.clear() ;
	build() ; 
}

// now recursive solution
vector < int > pip ; 

void go( int hh ){
	pip.clear() ;
	if( hh == dd.size() - 1 ){
		return ; 
	}
	go( hh + 1 ) ;
	// now sort and go once again
	vector < pair < int , int > > qu ;
	
	for( auto x : dd[ hh ] ){
		if( x.f == x.s ) continue ;
		int l = x.f , r = x.s ;
		int mid = ( l + r ) / 2 ;
		// l -- mid sorted, mid + 1 -- r sorted 
		// now unite 
		int pos = mid ; 
		for( int j = mid + 1 ; j <= r ; j ++ ){
			schedule( ans[ pos ] , ans[ j ] ) ;
			qu.pb( { pos , j } ) ;
			pos -- ;
		}
	}
	
	pip = visit() ;
	FOR( i , pip.size() ){
		int cur = pip[ i ] ;
		int a1 = qu[ i ].f , a2 = qu[ i ].s ;
		if( cur != 1 ){
			swap( ans[ a1 ] , ans[ a2 ] ) ;
		}
	}
	go( hh + 1 ) ; 
	return ; 
}

void solve( int n , int v ){
	ans.clear() ;
	ans.pb( - 1 ) ;
    for( int i = 1 ; i <= n ; i ++ ) ans.pb( i ) ;
    
    if( n != 1 ){
    	lst.clear() ; dd.clear() ; nxt.clear() ; 
    lst.pb( { 1 , n } ) ;
    build() ;
    go( 0 ) ;
    }
    
    
    vector < int > pas ;
    for( int i = 1 ; i <= n ; i ++ ) pas.pb( ans[ i ] ) ;
    answer( pas ) ;
    return ;

}
//signed main() {
//   ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
//   int t = 1 ; // cin >> t ;
//   while( t -- ){
//   	 solve() ;
//   }
//
//}

Compilation message (stderr)

swaps.cpp: In function 'void go(int)':
swaps.cpp:66:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  if( hh == dd.size() - 1 ){
      |      ~~~^~~~~~~~~~~~~~~~
swaps.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
   88 |  FOR( i , pip.size() ){
      |       ~~~~~~~~~~~~~~                     
swaps.cpp:88:2: note: in expansion of macro 'FOR'
   88 |  FOR( i , pip.size() ){
      |  ^~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3-1: 3 / 3
• Subtask 3-2: 2 / 2
• Subtask 4-1: 9 / 9
• Subtask 4-2: 6 / 6
• Subtask 5-1: 0 / 9
• Subtask 5-2: 0 / 6
• Subtask 6-1: 0 / 21
• Subtask 6-2: 0 / 14
• Subtask 7-1: 0 / 9
• Subtask 7-2: 0 / 6