oj.uz

답안 #465944

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
465944 2021-08-17T12:06:06 Z Tsovak Xor Sort (eJOI20_xorsort) C++17
65 / 100
 104 ms 1236 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 func(int x, int y)
{
	int i, j;
	for (i = y; i > x; i--) {
		ans.pb(mpr(i - 1, i));
		ans.pb(mpr(i, i - 1));
		ans.pb(mpr(i - 1, i));
		swap(a[i], a[i - 1]);
	}
	return;
}

void solve()
{
	int i, j;
	int s;
	cin >> n >> s;
	for (i = 1; i <= n; i++) {
		cin >> a[i];
	}
	if (s == 1) {
		int ind, mn;
		for (i = 1; i <= n; i++) {
			mn = MAX;
			for (j = i; j <= n; j++) {
				if (mn > a[j]) {
					mn = a[j];
					ind = j;
				}
			}
			func(i, ind);
		}
		cout << sz(ans) << endl;
		for (i = 0; i < sz(ans); i++) {
			cout << ans[i].ff << ' ' << ans[i].ss << endl;
		}
	}
	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;
}

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

Compilation message

xorsort.cpp: In function 'void func(int, int)':
xorsort.cpp:217:9: warning: unused variable 'j' [-Wunused-variable]
  217 |  int i, j;
      |         ^
xorsort.cpp: In function 'void solve()':
xorsort.cpp:245:8: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
  245 |    func(i, ind);
      |    ~~~~^~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 28 ms 640 KB Output is correct
5 Correct 30 ms 648 KB Output is correct
6 Correct 31 ms 680 KB Output is correct
7 Correct 31 ms 640 KB Output is correct
8 Correct 29 ms 632 KB Output is correct
9 Correct 36 ms 672 KB Output is correct
10 Correct 31 ms 592 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 61 ms 856 KB Output is correct
13 Correct 69 ms 976 KB Output is correct
14 Correct 65 ms 864 KB Output is correct
15 Correct 58 ms 852 KB Output is correct

Subtask #2
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 28 ms 640 KB Output is correct
5 Correct 30 ms 648 KB Output is correct
6 Correct 31 ms 680 KB Output is correct
7 Correct 31 ms 640 KB Output is correct
8 Correct 29 ms 632 KB Output is correct
9 Correct 36 ms 672 KB Output is correct
10 Correct 31 ms 592 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 61 ms 856 KB Output is correct
13 Correct 69 ms 976 KB Output is correct
14 Correct 65 ms 864 KB Output is correct
15 Correct 58 ms 852 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 29 ms 676 KB Output is correct
18 Correct 54 ms 888 KB Output is correct
19 Correct 51 ms 848 KB Output is correct
20 Correct 48 ms 768 KB Output is correct
21 Correct 50 ms 864 KB Output is correct
22 Correct 58 ms 876 KB Output is correct
23 Correct 65 ms 848 KB Output is correct
24 Correct 48 ms 860 KB Output is correct
25 Correct 55 ms 848 KB Output is correct
26 Incorrect 104 ms 1236 KB Integer 59568 violates the range [0, 40000]
27 Halted 0 ms 0 KB -

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 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 468 KB Output is correct
5 Correct 53 ms 868 KB Output is correct
6 Correct 56 ms 840 KB Output is correct
7 Correct 54 ms 928 KB Output is correct
8 Correct 56 ms 908 KB Output is correct
9 Correct 63 ms 940 KB Output is correct
10 Correct 54 ms 912 KB Output is correct
11 Correct 62 ms 884 KB Output is correct
12 Correct 57 ms 916 KB Output is correct
13 Correct 65 ms 924 KB Output is correct
14 Correct 58 ms 852 KB Output is correct
15 Correct 69 ms 972 KB Output is correct