oj.uz

Submission #1025346

# Submission time Handle Problem Language Result Execution time Memory
1025346 2024-07-16T22:29:12 Z tolbi Xor Sort (eJOI20_xorsort) C++17
40 / 100
 42 ms 1492 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,s;cin>>n>>s;
	vector<int> arr(n);
	for (int i = 0; i < n; ++i)
	{
		cin>>arr[i];
	}
	vector<int> barr = arr;
	vector<pair<int,int>> ansarr;
	for (int bit = 22; bit >= 0; bit--){
		for (int i = 0; i+1 < n; i++){
			if (arr[i]&(1LL<<bit)){
				if (arr[i+1]&(1LL<<bit)){
					ansarr.push_back({i+1,i+2});
					arr[i]^=arr[i+1];
				}
				else {
					ansarr.push_back({i+2,i+1});
					ansarr.push_back({i+1,i+2});
					arr[i+1]^=arr[i];
					arr[i]^=arr[i+1];
				}
			}
		}
		if ((n>=1) && (arr[n-1]&(1LL<<bit))){
			n--;
		}
	}
	cout<<ansarr.size()<<endl;
	for (int i = 0; i < ansarr.size(); ++i)
	{
		cout<<ansarr[i].first<<" "<<ansarr[i].second<<endl;
	}
}

Compilation message

xorsort.cpp: In function 'int32_t main()':
xorsort.cpp:35:20: 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]
   35 |  for (int i = 0; i < ansarr.size(); ++i)
      |                  ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 2 ms 348 KB Not sorted
4 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 2 ms 348 KB Not sorted
4 Halted 0 ms 0 KB -

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 692 KB Output is correct
5 Correct 33 ms 1204 KB Output is correct
6 Correct 31 ms 1280 KB Output is correct
7 Correct 30 ms 1236 KB Output is correct
8 Correct 30 ms 1240 KB Output is correct
9 Correct 31 ms 1236 KB Output is correct
10 Correct 31 ms 1232 KB Output is correct
11 Correct 35 ms 1120 KB Output is correct
12 Correct 32 ms 1492 KB Output is correct
13 Correct 32 ms 1152 KB Output is correct
14 Correct 37 ms 1240 KB Output is correct
15 Correct 42 ms 1492 KB Output is correct