oj.uz

Submission #959092

# Submission time Handle Problem Language Result Execution time Memory
959092 2024-04-07T13:25:04 Z lollipop The Collection Game (BOI21_swaps) C++17
35 / 100
 37 ms 1744 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 ) / 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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 3 ms 592 KB Correct
3 Correct 9 ms 452 KB Correct
4 Correct 33 ms 1232 KB Correct
5 Correct 36 ms 1468 KB Correct
6 Correct 35 ms 1468 KB Correct
7 Correct 33 ms 1712 KB Correct
8 Correct 33 ms 1720 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 3 ms 556 KB Correct
3 Correct 9 ms 452 KB Correct
4 Correct 34 ms 1744 KB Correct
5 Correct 34 ms 1468 KB Correct
6 Correct 36 ms 1216 KB Correct
7 Correct 33 ms 956 KB Correct
8 Correct 35 ms 1232 KB Correct
9 Correct 34 ms 1464 KB Correct
10 Correct 37 ms 1208 KB Correct
11 Correct 34 ms 1216 KB Correct
12 Correct 34 ms 960 KB Correct
13 Correct 35 ms 1460 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 444 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 444 KB Correct
3 Correct 0 ms 344 KB Correct
4 Correct 2 ms 616 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 616 KB Correct
3 Correct 9 ms 452 KB Correct
4 Correct 33 ms 1400 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 616 KB Correct
3 Correct 9 ms 452 KB Correct
4 Correct 33 ms 1400 KB Correct
5 Correct 0 ms 344 KB Correct
6 Correct 2 ms 452 KB Correct
7 Correct 9 ms 456 KB Correct
8 Correct 35 ms 960 KB Correct
9 Correct 32 ms 1476 KB Correct
10 Correct 32 ms 1232 KB Correct
11 Correct 35 ms 1472 KB Correct
12 Correct 32 ms 988 KB Correct
13 Correct 1 ms 344 KB Correct
14 Correct 3 ms 616 KB Correct
15 Correct 10 ms 456 KB Correct
16 Correct 34 ms 1712 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 616 KB Correct
3 Correct 9 ms 460 KB Correct
4 Correct 33 ms 1236 KB Correct
5 Runtime error 32 ms 1476 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 616 KB Correct
3 Correct 9 ms 460 KB Correct
4 Correct 33 ms 1236 KB Correct
5 Runtime error 32 ms 1476 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 600 KB Correct
3 Correct 11 ms 704 KB Correct
4 Correct 32 ms 960 KB Correct
5 Runtime error 31 ms 968 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 600 KB Correct
3 Correct 11 ms 704 KB Correct
4 Correct 32 ms 960 KB Correct
5 Runtime error 31 ms 968 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 600 KB Correct
3 Correct 9 ms 452 KB Correct
4 Correct 34 ms 1484 KB Correct
5 Runtime error 33 ms 984 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 600 KB Correct
3 Correct 9 ms 452 KB Correct
4 Correct 34 ms 1484 KB Correct
5 Runtime error 33 ms 984 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -