oj.uz

Submission #959102

# Submission time Handle Problem Language Result Execution time Memory
959102 2024-04-07T13:34:32 Z lollipop The Collection Game (BOI21_swaps) C++17
35 / 100
 39 ms 1732 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 ){
	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 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 ] ) ;
		}
	}
	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 ++ )
......
   94 |  FOR( i , pip.size() ){
      |       ~~~~~~~~~~~~~~                     
swaps.cpp:94:2: note: in expansion of macro 'FOR'
   94 |  FOR( i , pip.size() ){
      |  ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Correct
2 Correct 3 ms 344 KB Correct
3 Correct 10 ms 344 KB Correct
4 Correct 34 ms 976 KB Correct
5 Correct 31 ms 1220 KB Correct
6 Correct 36 ms 952 KB Correct
7 Correct 34 ms 1452 KB Correct
8 Correct 34 ms 948 KB Correct

Subtask #2
10.0 / 10.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 36 ms 1204 KB Correct
5 Correct 36 ms 1204 KB Correct
6 Correct 32 ms 1456 KB Correct
7 Correct 36 ms 1480 KB Correct
8 Correct 35 ms 1448 KB Correct
9 Correct 39 ms 1200 KB Correct
10 Correct 36 ms 1232 KB Correct
11 Correct 35 ms 1208 KB Correct
12 Correct 38 ms 1456 KB Correct
13 Correct 36 ms 1208 KB Correct

Subtask #3-1
3.0 / 3.0

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

Subtask #4-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 2 ms 496 KB Correct
3 Correct 9 ms 344 KB Correct
4 Correct 32 ms 1708 KB Correct
5 Correct 1 ms 344 KB Correct
6 Correct 2 ms 344 KB Correct
7 Correct 10 ms 344 KB Correct
8 Correct 35 ms 1200 KB Correct
9 Correct 37 ms 960 KB Correct
10 Correct 38 ms 1204 KB Correct
11 Correct 39 ms 1212 KB Correct
12 Correct 33 ms 1456 KB Correct
13 Correct 0 ms 344 KB Correct
14 Correct 2 ms 344 KB Correct
15 Correct 11 ms 344 KB Correct
16 Correct 34 ms 1704 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 9 ms 344 KB Correct
4 Correct 37 ms 1228 KB Correct
5 Runtime error 37 ms 976 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 9 ms 344 KB Correct
4 Correct 37 ms 1228 KB Correct
5 Runtime error 37 ms 976 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 0 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 9 ms 344 KB Correct
4 Correct 38 ms 1732 KB Correct
5 Runtime error 36 ms 1216 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 0 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 9 ms 344 KB Correct
4 Correct 38 ms 1732 KB Correct
5 Runtime error 36 ms 1216 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 0 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 9 ms 344 KB Correct
4 Correct 32 ms 1208 KB Correct
5 Runtime error 36 ms 1452 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 0 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 9 ms 344 KB Correct
4 Correct 32 ms 1208 KB Correct
5 Runtime error 36 ms 1452 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -