oj.uz

Submission #959114

# Submission time Handle Problem Language Result Execution time Memory
959114 2024-04-07T13:47:26 Z lollipop The Collection Game (BOI21_swaps) C++17
35 / 100
 37 ms 1712 KB 
#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 ss = ( r - l + 1 ) ; 
			int mid = l + ( ss + 1 ) / 2 - 1 ;
			nxt.pb( { l , mid } ) ;
			nxt.pb( { mid + 1 , r } ) ;
		}
	}
	lst = nxt ; nxt.clear() ;
	build() ; 
	return ; 
}

// now recursive solution
vector < int > pip ; 
vector < pair < int , int > > qu ;


void go( int hh ){
	if( hh == dd.size() - 1 ){
		return ; 
	}
	int hh1 = hh + 1 ;
	go( hh1 ) ;
	// now sort and go once again
	pip.clear() ;
	qu.clear() ; 
	
	for( auto x : dd[ hh ] ){
		if( x.f == x.s ) continue ;
		int l = x.f , r = x.s ;
		int ss = ( r - l + 1 ) ; 
		int mid = l + ( ss + 1 ) / 2 - 1 ;
		
		// 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 ] ) ;
		}
	}
	
	hh1 = hh + 1 ;
	go( hh1 ) ; 
	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

swaps.cpp: In function 'void go(int)':
swaps.cpp:69: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]
   69 |  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 ++ )
......
   95 |  FOR( i , pip.size() ){
      |       ~~~~~~~~~~~~~~                     
swaps.cpp:95:2: note: in expansion of macro 'FOR'
   95 |  FOR( i , pip.size() ){
      |  ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 10 ms 344 KB Correct
4 Correct 34 ms 1484 KB Correct
5 Correct 32 ms 1212 KB Correct
6 Correct 32 ms 720 KB Correct
7 Correct 36 ms 1712 KB Correct
8 Correct 35 ms 1232 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 9 ms 344 KB Correct
4 Correct 35 ms 1204 KB Correct
5 Correct 34 ms 1204 KB Correct
6 Correct 33 ms 1204 KB Correct
7 Correct 32 ms 956 KB Correct
8 Correct 34 ms 1456 KB Correct
9 Correct 35 ms 1188 KB Correct
10 Correct 32 ms 980 KB Correct
11 Correct 32 ms 1216 KB Correct
12 Correct 33 ms 1224 KB Correct
13 Correct 36 ms 1208 KB Correct

Subtask #3-1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct

Subtask #3-2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 2 ms 344 KB Correct

Subtask #4-1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 9 ms 344 KB Correct
4 Correct 34 ms 1436 KB Correct

Subtask #4-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 9 ms 344 KB Correct
4 Correct 34 ms 1436 KB Correct
5 Correct 0 ms 344 KB Correct
6 Correct 3 ms 344 KB Correct
7 Correct 11 ms 344 KB Correct
8 Correct 34 ms 1200 KB Correct
9 Correct 33 ms 1452 KB Correct
10 Correct 34 ms 972 KB Correct
11 Correct 33 ms 1696 KB Correct
12 Correct 33 ms 1456 KB Correct
13 Correct 1 ms 344 KB Correct
14 Correct 2 ms 500 KB Correct
15 Correct 9 ms 344 KB Correct
16 Correct 37 ms 1208 KB Correct

Subtask #5-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 9 ms 344 KB Correct
4 Correct 36 ms 1456 KB Correct
5 Runtime error 32 ms 1704 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #5-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 9 ms 344 KB Correct
4 Correct 36 ms 1456 KB Correct
5 Runtime error 32 ms 1704 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 9 ms 344 KB Correct
4 Correct 34 ms 1204 KB Correct
5 Runtime error 36 ms 1188 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #6-2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 9 ms 344 KB Correct
4 Correct 34 ms 1204 KB Correct
5 Runtime error 36 ms 1188 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #7-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 9 ms 344 KB Correct
4 Correct 37 ms 1228 KB Correct
5 Runtime error 33 ms 1456 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #7-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 9 ms 344 KB Correct
4 Correct 37 ms 1228 KB Correct
5 Runtime error 33 ms 1456 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -