oj.uz

답안 #563357

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
563357 2022-05-17T02:56:39 Z minhcool Swap (BOI16_swap) C++17
48 / 100
 11 ms 4384 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 = 2e3 + 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 2 ms 1492 KB Output is correct
5 Correct 2 ms 1492 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 2 ms 1492 KB Output is correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 2 ms 1620 KB Output is correct
10 Correct 1 ms 1620 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 2 ms 1492 KB Output is correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 2 ms 1620 KB Output is correct
10 Correct 1 ms 1620 KB Output is correct
11 Correct 10 ms 4308 KB Output is correct
12 Correct 9 ms 4308 KB Output is correct
13 Correct 9 ms 4308 KB Output is correct
14 Correct 11 ms 4308 KB Output is correct
15 Correct 11 ms 4384 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 2 ms 1492 KB Output is correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 2 ms 1620 KB Output is correct
10 Correct 1 ms 1620 KB Output is correct
11 Correct 10 ms 4308 KB Output is correct
12 Correct 9 ms 4308 KB Output is correct
13 Correct 9 ms 4308 KB Output is correct
14 Correct 11 ms 4308 KB Output is correct
15 Correct 11 ms 4384 KB Output is correct
16 Runtime error 3 ms 3024 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 2 ms 1492 KB Output is correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 2 ms 1620 KB Output is correct
10 Correct 1 ms 1620 KB Output is correct
11 Correct 10 ms 4308 KB Output is correct
12 Correct 9 ms 4308 KB Output is correct
13 Correct 9 ms 4308 KB Output is correct
14 Correct 11 ms 4308 KB Output is correct
15 Correct 11 ms 4384 KB Output is correct
16 Runtime error 3 ms 3024 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -