oj.uz

Submission #959098

# Submission time Handle Problem Language Result Execution time Memory
959098 2024-04-07T13:31:52 Z lollipop The Collection Game (BOI21_swaps) C++17
25 / 100
 44 ms 960 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 mid = ( l + r + 1 ) / 2 ;
		    if( mid == r ) mid -- ;
			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 ){
	pip.clear() ;
	if( hh == dd.size() - 1 ){
		return ; 
	}
	go( hh + 1 ) ;
	// now sort and go once again
	qu.clear() ; 
	
	for( auto x : dd[ hh ] ){
		if( x.f == x.s ) continue ;
		int l = x.f , r = x.s ;
		int mid = ( l + r + 1 ) / 2 ;
		if( mid == r ) mid -- ;
		// 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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 3 ms 344 KB Correct
3 Correct 11 ms 456 KB Correct
4 Correct 38 ms 704 KB Correct
5 Correct 38 ms 480 KB Correct
6 Correct 41 ms 884 KB Correct
7 Correct 37 ms 708 KB Correct
8 Correct 39 ms 704 KB Correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 3 ms 344 KB Correct
3 Correct 11 ms 456 KB Correct
4 Correct 39 ms 596 KB Correct
5 Correct 42 ms 480 KB Correct
6 Correct 38 ms 476 KB Correct
7 Correct 38 ms 604 KB Correct
8 Correct 44 ms 960 KB Correct
9 Runtime error 41 ms 708 KB Execution killed with signal 13
10 Halted 0 ms 0 KB -

Subtask #3-1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 3 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 3 ms 344 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 3 ms 344 KB Correct

Subtask #4-1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 3 ms 344 KB Correct
3 Correct 12 ms 456 KB Correct
4 Correct 38 ms 480 KB Correct

Subtask #4-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 3 ms 344 KB Correct
3 Correct 12 ms 456 KB Correct
4 Correct 38 ms 480 KB Correct
5 Correct 1 ms 344 KB Correct
6 Correct 3 ms 344 KB Correct
7 Correct 11 ms 460 KB Correct
8 Correct 42 ms 704 KB Correct
9 Correct 39 ms 708 KB Correct
10 Correct 39 ms 728 KB Correct
11 Correct 40 ms 480 KB Correct
12 Correct 39 ms 708 KB Correct
13 Correct 1 ms 344 KB Correct
14 Correct 3 ms 344 KB Correct
15 Correct 11 ms 456 KB Correct
16 Correct 39 ms 476 KB Correct

Subtask #5-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 3 ms 344 KB Correct
3 Correct 11 ms 464 KB Correct
4 Correct 39 ms 484 KB Correct
5 Runtime error 19 ms 476 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 1 ms 344 KB Correct
2 Correct 3 ms 344 KB Correct
3 Correct 11 ms 464 KB Correct
4 Correct 39 ms 484 KB Correct
5 Runtime error 19 ms 476 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 3 ms 344 KB Correct
3 Correct 12 ms 460 KB Correct
4 Correct 39 ms 704 KB Correct
5 Runtime error 19 ms 728 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 3 ms 344 KB Correct
3 Correct 12 ms 460 KB Correct
4 Correct 39 ms 704 KB Correct
5 Runtime error 19 ms 728 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 3 ms 344 KB Correct
3 Correct 13 ms 464 KB Correct
4 Correct 40 ms 476 KB Correct
5 Runtime error 21 ms 480 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 3 ms 344 KB Correct
3 Correct 13 ms 464 KB Correct
4 Correct 40 ms 476 KB Correct
5 Runtime error 21 ms 480 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -