Submission #734156

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

swap

#include<bits/stdc++.h>
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<int> dp[N][35];
map<int, int> mp[N];
 
vector<int> merge(vector<int> a, vector<int> b, int i){
	vector<int> c(a.size() + b.size());
	int itr1 = 0, itr2 = 0, itr3 = 0;
	queue<pair<int, bool>> q;
	q.push({i << 1, 0}), q.push({i << 1 | 1, 1});
	while(!q.empty()){
	    int u = q.front().fi, type = q.front().se;
	    q.pop();
	    if(!type){
	        c[itr3] = a[itr1];
	        itr1++, itr3++;
	    }
	    else{
	        c[itr3] = b[itr2];
	        itr2++, itr3++;
	    }
	    if((u << 1) <= n) q.push({(u << 1), (bool)type});
	    if((u << 1 | 1) <= n) q.push({(u << 1 | 1), (bool)type});
	}
	return c;
	/*
	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(){
	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(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(min(j, arr[i * 2]));
				dp[i][it.se].pb(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<int> temp = merge(dp[i * 2][temp1], dp[i * 2 + 1][temp2], i);
					dp[i][ind].pb(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<int> temp = merge(dp[i * 2][temp2], dp[i * 2 + 1][temp1], i);
					dp[i][ind].pb(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<int> temp1 = merge(dp[i * 2][mp[i * 2][j]], dp[i * 2 + 1][tempo1], i), temp2 = merge(dp[i * 2][tempo2], dp[i * 2 + 1][mp[i * 2 + 1][j]], i);
					dp[i][ind].pb(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] != temp2[i]){
							ck = (temp1[i] < temp2[i]);
							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].shrink_to_fit();
            for(int j = 1; j <= mp[i * 2 + 1].size(); j++) dp[i * 2 + 1][j].shrink_to_fit();
        }
	}
	for(auto it : dp[1][mp[1][arr[1]]]) cout << it << " ";
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

Compilation message (stderr)

swap.cpp:14:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   14 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
swap.cpp: In function 'void process()':
swap.cpp:126:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |      for(int i = 0; i < temp1.size(); i++){
      |                     ~~^~~~~~~~~~~~~~
swap.cpp:137:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |             for(int j = 1; j <= mp[i * 2].size(); j++) dp[i * 2][j].shrink_to_fit();
      |                            ~~^~~~~~~~~~~~~~~~~~~
swap.cpp:138:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |             for(int j = 1; j <= mp[i * 2 + 1].size(); j++) dp[i * 2 + 1][j].shrink_to_fit();
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~

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