oj.uz

Submission #465932

# Submission time Handle Problem Language Result Execution time Memory
465932 2021-08-17T11:20:48 Z Tsovak Xor Sort (eJOI20_xorsort) C++17
40 / 100
 68 ms 1036 KB 
// -------------------- Includes -------------------- //
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <array>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <tuple>
#include <utility>
#include <cassert>
#include <assert.h>
#include <climits>
#include <limits.h>
#include <ctime>
#include <time.h>
#include <random>
#include <chrono>
#include <fstream>
using namespace std;

// -------------------- Typedefs -------------------- //

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;

// -------------------- Defines -------------------- //

#define pr pair
#define mpr make_pair
#define ff first
#define ss second

#define mset multiset
#define mmap multimap
#define uset unordered_set
#define umap unordered_map
#define umset unordered_multiset
#define ummap unordered_multimap
#define pqueue priority_queue

#define sz(x) (int((x).size()))
#define len(x) (int((x).length()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()

#define pf push_front
#define pb push_back
#define popf pop_front
#define popb pop_back
#define ft front
#define bk back

#define lb lower_bound
#define ub upper_bound
#define bs binary_search

// -------------------- Constants -------------------- //

const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18 + 5);
const ll MOD = ll(1e9 + 7);
const ll MOD2 = ll(998244353);

// -------------------- Functions -------------------- //

void fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	return;
}

void precision(int x)
{
	cout.setf(ios::fixed | ios::showpoint);
	cout.precision(x);
	return;
}

ll gcd(ll a, ll b)
{
	if (a > b) {
		swap(a, b);
	}
	if (a == 0) {
		return b;
	}
	if (a == b) {
		return a;
	}
	return gcd(b % a, a);
}

ll lcm(ll a, ll b)
{
	return a / gcd(a, b) * b;
}

bool is_prime(ll a)
{
	int i;
	for (i = 2; i * i <= a; i++) {
		if (a % ll(i) == 0) {
			return false;
		}
	}
	return true;
}

bool is_square(ll a)
{
	ll b = ll(sqrt(a));
	return (b * b == a);
}

bool is_cube(ll a)
{
	ll b = ll(cbrt(a));
	return (b * b * b == a);
}

int digit_sum(ll a)
{
	int sum = 0;
	while (a) {
		sum += int(a % 10);
		a /= 10;
	}
	return sum;
}

ll binpow(ll a, int b)
{
	ll ans = 1;
	while (b) {
		if ((b & 1) == 1) {
			ans *= a;
		}
		b >>= 1;
		a *= a;
	}
	return ans;
}

ll binpow_by_mod(ll a, ll b, ll mod)
{
	ll ans = 1;
	while (b) {
		if ((b & 1) == 1) {
			ans *= a;
			ans %= mod;
		}
		b >>= 1;
		a *= a;
		a %= mod;
	}
	return ans;
}

ll factorial(int a)
{
	int i;
	ll ans = 1;
	for (i = 2; i <= a; i++) {
		ans *= ll(i);
	}
	return ans;
}

ll factorial_by_mod(int a, ll mod)
{
	int i;
	ll ans = 1;
	for (i = 2; i <= a; i++) {
		ans *= ll(i);
		ans %= mod;
	}
	return ans;
}

// -------------------- Solution -------------------- //

const int N = 1005;
int a[N];
int n;

set<int> st;

vector<pr<int, int>> ans;

void solve()
{
	int i, j;
	int s;
	cin >> n >> s;
	for (i = 1; i <= n; i++) {
		cin >> a[i];
	}
	if (s == 1) {

	}
	else {
		for (i = 19; i >= 0; i--) {
			clr(st);
			for (j = 1; j <= n; j++) {
				if ((a[j] & (1 << i))) {
					st.insert(j);
				}
			}
			if (!st.empty()) {
				while (!st.empty()) {
					j = (*st.begin());
					st.erase(st.begin());
					if (j == n) {
						break;
					}
					if (st.find(j + 1) == st.end()) {
						st.insert(j);
						st.insert(j + 1);
						ans.pb(mpr(j + 1, j));
						a[j + 1] ^= a[j];
						//cout << j + 1 << ' ' << j << ' ' << i << endl;
					}
					else {
						st.insert(j + 1);
						ans.pb(mpr(j, j + 1));
						a[j] ^= a[j + 1];
						//cout << j << ' ' << j + 1 << ' ' << i << endl;
					}
				}
				n--;
			}
		}
		cout << sz(ans) << endl;
		for (i = 0; i < sz(ans); i++) {
			cout << ans[i].ff << ' ' << ans[i].ss << endl;
		}
	}
	return;
}

void precalc()
{
	return;
}

int main()
{
	fastio();

	precalc();

	int tests = 1, tc;
	//cin >> tests;
	for (tc = 1; tc <= tests; tc++) {
		solve();
	}

	//cout << db(clock()) / CLOCKS_PER_SEC << endl;

	return 0;
}

/*
	# # # #   # # # #   # # # #   #       #    #       #     #
	   #      #         #     #    #     #    # #      #   #
	   #      # # # #   #     #     #   #    #   #     # #
	   #            #   #     #      # #    # # # #    #   #
	   #      # # # #   # # # #       #    #       #   #     #
*/

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 11 ms 456 KB Output is correct
5 Correct 57 ms 908 KB Output is correct
6 Correct 57 ms 936 KB Output is correct
7 Correct 54 ms 868 KB Output is correct
8 Correct 55 ms 840 KB Output is correct
9 Correct 54 ms 972 KB Output is correct
10 Correct 53 ms 852 KB Output is correct
11 Correct 53 ms 820 KB Output is correct
12 Correct 56 ms 892 KB Output is correct
13 Correct 55 ms 912 KB Output is correct
14 Correct 60 ms 944 KB Output is correct
15 Correct 68 ms 1036 KB Output is correct