oj.uz

Submission #409178

# Submission time Handle Problem Language Result Execution time Memory
409178 2021-05-20T10:00:02 Z oolimry MalnaRISC (COI21_malnarisc) C++17
60 / 100
 2 ms 380 KB 
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define s first
#define v second
typedef long long lint;
typedef pair<lint,lint> ii;
 
 int n; 
vector<vector<ii> > ensures;
int arr[102390];
int reall[102390];
int pos[102390];
 
void put(int a, int b){ ///ensure a < b
	if(arr[a] > arr[b]){
		swap(arr[a],arr[b]);
	}
	
	if(not reall[a] and reall[b]){ ///a and b will be swapped
		swap(reall[a], reall[b]);
		swap(pos[a], pos[b]);
	}
	
	if(reall[a] and reall[b]){
		ensures.back().push_back(ii(pos[a], pos[b]));
	}
	
	//if(a < n and b < n) ensures.back().push_back(ii(a,b));
}
 
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n;
	int B = 0;
	while((1<<B) < n) B++;
	int N = 1<<B;
	
	for(int i = 0;i < N;i++) arr[i] = min(n,i);
	random_shuffle(arr,arr+n);
	for(int i = 0;i < n;i++) reall[i] = 1;
	for(int i = 0;i < n;i++) pos[i] = i;
	
	for(int a = 1;a <= B;a++){
		for(int b = a-1;b >= 0;b--){
			ensures.push_back({});
			
			for(int i = 0;i < N;i++){
				if(i & (1<<b)) continue;
				int block = (i >> a);
				if(block & 1){
					put(i+(1<<b), i);
				}
				else{
					put(i, i+(1<<b));
				}
			}
			
		}
	}
	
	vector<vector<ii> > ans;
	
	for(auto er : ensures){
		ans.push_back({});
		
		for(ii v : er){			
			ans.back().push_back(ii(v.first+1, v.second+1));
		}
		
		if(ans.back().empty()) ans.pop_back();
	}
	
	cout << sz(ans) << '\n';
	for(auto er : ans){		
		for(ii v : er){
			cout << "CMPSWP R" << v.first << " R" << v.second << " ";
		}
		cout << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 380 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB not sorted

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB not sorted

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB not sorted

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB not sorted

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct