oj.uz

Submission #563358

# Submission time Handle Problem Language Result Execution time Memory
563358 2022-05-17T02:56:53 Z minhcool Swap (BOI16_swap) C++17
48 / 100
 585 ms 262144 KB 
#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<ii> dp[N][25];
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(){
	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 <= n; j++){
            //cout << i << " " << j << "\n";
            //for(auto it : dp[i][j]) cout << it.fi << " " << it.se << "\n";
            //cout << "\n";
        }
	}
	for(auto it : dp[1][mp[1][arr[1]]]) cout << it.se << " ";
}

signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

Compilation message

swap.cpp: In function 'std::vector<std::pair<long long int, long long int> > merge(std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >)':
swap.cpp:26:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  while(itr1 < a.size() || itr2 < b.size()){
      |        ~~~~~^~~~~~~~~~
swap.cpp:26:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  while(itr1 < a.size() || itr2 < b.size()){
      |                           ~~~~~^~~~~~~~~~
swap.cpp:27:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   if(itr1 == a.size()){
      |      ~~~~~^~~~~~~~~~~
swap.cpp:31:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   else if(itr2 == b.size()){
      |           ~~~~~^~~~~~~~~~~
swap.cpp: In function 'void process()':
swap.cpp:108:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |      for(int i = 0; i < temp1.size(); i++){
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 127132 KB Output is correct
2 Correct 61 ms 127052 KB Output is correct
3 Correct 60 ms 127056 KB Output is correct
4 Correct 60 ms 127136 KB Output is correct
5 Correct 62 ms 127072 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 127132 KB Output is correct
2 Correct 61 ms 127052 KB Output is correct
3 Correct 60 ms 127056 KB Output is correct
4 Correct 60 ms 127136 KB Output is correct
5 Correct 62 ms 127072 KB Output is correct
6 Correct 61 ms 127084 KB Output is correct
7 Correct 66 ms 127152 KB Output is correct
8 Correct 60 ms 127052 KB Output is correct
9 Correct 62 ms 127160 KB Output is correct
10 Correct 65 ms 127072 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 127132 KB Output is correct
2 Correct 61 ms 127052 KB Output is correct
3 Correct 60 ms 127056 KB Output is correct
4 Correct 60 ms 127136 KB Output is correct
5 Correct 62 ms 127072 KB Output is correct
6 Correct 61 ms 127084 KB Output is correct
7 Correct 66 ms 127152 KB Output is correct
8 Correct 60 ms 127052 KB Output is correct
9 Correct 62 ms 127160 KB Output is correct
10 Correct 65 ms 127072 KB Output is correct
11 Correct 76 ms 129924 KB Output is correct
12 Correct 85 ms 129928 KB Output is correct
13 Correct 67 ms 129848 KB Output is correct
14 Correct 69 ms 129908 KB Output is correct
15 Correct 66 ms 129928 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 127132 KB Output is correct
2 Correct 61 ms 127052 KB Output is correct
3 Correct 60 ms 127056 KB Output is correct
4 Correct 60 ms 127136 KB Output is correct
5 Correct 62 ms 127072 KB Output is correct
6 Correct 61 ms 127084 KB Output is correct
7 Correct 66 ms 127152 KB Output is correct
8 Correct 60 ms 127052 KB Output is correct
9 Correct 62 ms 127160 KB Output is correct
10 Correct 65 ms 127072 KB Output is correct
11 Correct 76 ms 129924 KB Output is correct
12 Correct 85 ms 129928 KB Output is correct
13 Correct 67 ms 129848 KB Output is correct
14 Correct 69 ms 129908 KB Output is correct
15 Correct 66 ms 129928 KB Output is correct
16 Runtime error 585 ms 262144 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 127132 KB Output is correct
2 Correct 61 ms 127052 KB Output is correct
3 Correct 60 ms 127056 KB Output is correct
4 Correct 60 ms 127136 KB Output is correct
5 Correct 62 ms 127072 KB Output is correct
6 Correct 61 ms 127084 KB Output is correct
7 Correct 66 ms 127152 KB Output is correct
8 Correct 60 ms 127052 KB Output is correct
9 Correct 62 ms 127160 KB Output is correct
10 Correct 65 ms 127072 KB Output is correct
11 Correct 76 ms 129924 KB Output is correct
12 Correct 85 ms 129928 KB Output is correct
13 Correct 67 ms 129848 KB Output is correct
14 Correct 69 ms 129908 KB Output is correct
15 Correct 66 ms 129928 KB Output is correct
16 Runtime error 585 ms 262144 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -