Submission #734051

#	Time	Username	Problem	Language	Result	Execution time	Memory
734051		minhcool	Swap (BOI16_swap)	C++17	48 / 100	404 ms	262144 KiB

swap

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
//#define int long long
#define fi first
#define se second
#define pb push_back
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 2e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n;
int arr[N];
 
// if initially arr[i] = j, what is the minimum array?
vector<ii> dp[N][19];
unordered_map<int, int> mp[N];
 
vector<ii> merge(vector<ii> a, vector<ii> b){
	vector<ii> c;
	int itr1 = 0, itr2 = 0;
	while(itr1 < a.size() || itr2 < b.size()){
		if(itr1 == a.size()){
			c.pb(b[itr2]);
			itr2++;
		}
		else if(itr2 == b.size()){
			c.pb(a[itr1]);
			itr1++;
		}
		else if(a[itr1].fi < b[itr2].fi){
			c.pb(a[itr1]);
			itr1++;
		}
		else{
			c.pb(b[itr2]);
			itr2++;
		}
	}
	return c;
}
 
void ins(int i, int j){
    if(mp[i].find(j) != mp[i].end()) return;
    mp[i][j] = 0;
    mp[i][j] = mp[i].size();
}
 
void process(){
   // cout << sizeof mp[1] << "\n";
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> arr[i];
	//cout << "OK\n";
	//return;
	for(int i = 1; i <= n; i++){
        int itr = i;
        mp[i][arr[i]] = 1;
        while(itr != 1){
            itr /= 2;
            ins(i, arr[itr]);
            ins(i, arr[itr << 1]);
            ins(i, arr[itr << 1 | 1]);
            //if(itr == 1) break;
        }
	}
	//return;
	for(int i = n; i >= 1; i--){
		if(i * 2 > n){
			//for(int j = 1; j <= n; j++) dp[i][j].pb({i, j});
			for(auto it : mp[i]) dp[i][it.se].pb({i, it.fi});
		}
		else if(i * 2 + 1 > n){
			for(auto it : mp[i]){
                int j = it.fi;
				//if(j == arr[i * 2]) continue;
				dp[i][it.se].pb({i, min(j, arr[i * 2])});
				dp[i][it.se].pb({i * 2, max(j, arr[i * 2])});
			}
		}
		else{//continue;
			for(auto it1 : mp[i]){
                int ind = it1.se, j = it1.fi;
				int temp = min(j, min(arr[i * 2], arr[i * 2 + 1]));
				//cout << i << " " << j << " " << temp << "\n";
				if(temp == j){// no swapping
                    int temp1 = mp[i * 2][arr[i * 2]], temp2 = mp[i * 2 + 1][arr[i * 2 + 1]];
					vector<ii> temp = merge(dp[i * 2][temp1], dp[i * 2 + 1][temp2]);
					dp[i][ind].pb({i, j});
					for(auto it : temp) dp[i][ind].pb(it);
				}
				else if(temp == arr[i * 2]){
                    //cout << "OK\n";
                    int temp1 = mp[i * 2 + 1][arr[i * 2 + 1]], temp2 = mp[i * 2][j];
					vector<ii> temp = merge(dp[i * 2][temp2], dp[i * 2 + 1][temp1]);
					dp[i][ind].pb({i, arr[i * 2]});
					for(auto it : temp) dp[i][ind].pb(it);
				}
				else{
                        //continue;
                    int tempo1 = mp[i * 2 + 1][arr[i * 2]], tempo2 = mp[i * 2][arr[i * 2]];
					vector<ii> temp1 = merge(dp[i * 2][mp[i * 2][j]], dp[i * 2 + 1][tempo1]), temp2 = merge(dp[i * 2][tempo2], dp[i * 2 + 1][mp[i * 2 + 1][j]]);
					dp[i][ind].pb({i, arr[i * 2 + 1]});
					bool ck = 0;
					assert(temp1.size() == temp2.size());
					for(int i = 0; i < temp1.size(); i++){
						assert(temp1[i].fi == temp2[i].fi);
						if(temp1[i].se != temp2[i].se){
							ck = (temp1[i].se < temp2[i].se);
							break;
						}
					}
					if(!ck) for(auto it : temp2) dp[i][ind].pb(it);
					else for(auto it : temp1) dp[i][ind].pb(it);
                }
            }
            for(int j = 1; j <= mp[i * 2].size(); j++) dp[i * 2][j].clear();
            for(int j = 1; j <= mp[i * 2 + 1].size(); j++) dp[i * 2 + 1][j].clear();
        }
	}
	for(auto it : dp[1][mp[1][arr[1]]]) cout << it.se << " ";
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

Compilation message (stderr)

swap.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
swap.cpp: In function 'std::vector<std::pair<int, int> > merge(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
swap.cpp:28:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  while(itr1 < a.size() || itr2 < b.size()){
      |        ~~~~~^~~~~~~~~~
swap.cpp:28:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  while(itr1 < a.size() || itr2 < b.size()){
      |                           ~~~~~^~~~~~~~~~
swap.cpp:29:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   if(itr1 == a.size()){
      |      ~~~~~^~~~~~~~~~~
swap.cpp:33:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   else if(itr2 == b.size()){
      |           ~~~~~^~~~~~~~~~~
swap.cpp: In function 'void process()':
swap.cpp:111:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |      for(int i = 0; i < temp1.size(); i++){
      |                     ~~^~~~~~~~~~~~~~
swap.cpp:122:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::unordered_map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |             for(int j = 1; j <= mp[i * 2].size(); j++) dp[i * 2][j].clear();
      |                            ~~^~~~~~~~~~~~~~~~~~~
swap.cpp:123:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::unordered_map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |             for(int j = 1; j <= mp[i * 2 + 1].size(); j++) dp[i * 2 + 1][j].clear();
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 0 / 20
• Subtask 5: 0 / 32