oj.uz

Submission #668704

# Submission time Handle Problem Language Result Execution time Memory
668704 2022-12-04T14:31:49 Z sysia Sob (COCI19_sob) C++17
110 / 110
 556 ms 86044 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
const int oo = 1e18, oo2 = 1e9+7, K = 20;
const int mod = 998244353;

void rec(vector<int>a, vector<int>b, int bit){
	assert(a.size() == b.size());
	int n = (int)a.size();
	if (bit < 0){
		for (int i = 0; i<n; i++){
			cout << a[i] << " " << b[i] << "\n";
		}
		return;
	}
	vector<vector<int>>A(2), B(2);
	for (auto v: a)	A[(bool)(v&(1<<bit))].emplace_back(v);
	for (auto v: b)	B[(bool)(v&(1<<bit))].emplace_back(v);
	// debug(A, B);
	int diff = A[0].size()-B[0].size();
	assert(diff >= 0);
	rotate(A[0].begin(), A[0].begin()+diff, A[0].end());
	vector<int>mv;
	for (int i = 0; i<diff; i++){
		mv.emplace_back(A[0].back());
		A[0].pop_back();
	}
	reverse(mv.begin(), mv.end());
	for (auto x: A[1]) mv.emplace_back(x);
	A[1] = mv;
	// debug(A, B);
	rec(A[0], B[0], bit-1);
	rec(A[1], B[1], bit-1);
}

void solve(){
	int n, m; cin >> n >> m;
	vector<int>a, b;
	for (int i = 0; i<n; i++){
		a.emplace_back(i);
		b.emplace_back(m+i);
	}
	rec(a, b, K);
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	solve();
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 384 KB Output is correct
2 Correct 143 ms 348 KB Output is correct
3 Correct 142 ms 324 KB Output is correct
4 Correct 359 ms 56052 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 1748 KB Output is correct
2 Correct 162 ms 420 KB Output is correct
3 Correct 151 ms 420 KB Output is correct
4 Correct 144 ms 212 KB Output is correct
5 Correct 141 ms 576 KB Output is correct
6 Correct 359 ms 55176 KB Output is correct
7 Correct 249 ms 33416 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 332 KB Output is correct
2 Correct 148 ms 432 KB Output is correct
3 Correct 144 ms 340 KB Output is correct
4 Correct 145 ms 500 KB Output is correct
5 Correct 144 ms 340 KB Output is correct
6 Correct 146 ms 552 KB Output is correct
7 Correct 167 ms 552 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 384 KB Output is correct
2 Correct 143 ms 348 KB Output is correct
3 Correct 142 ms 324 KB Output is correct
4 Correct 359 ms 56052 KB Output is correct
5 Correct 150 ms 1748 KB Output is correct
6 Correct 162 ms 420 KB Output is correct
7 Correct 151 ms 420 KB Output is correct
8 Correct 144 ms 212 KB Output is correct
9 Correct 141 ms 576 KB Output is correct
10 Correct 359 ms 55176 KB Output is correct
11 Correct 249 ms 33416 KB Output is correct
12 Correct 151 ms 332 KB Output is correct
13 Correct 148 ms 432 KB Output is correct
14 Correct 144 ms 340 KB Output is correct
15 Correct 145 ms 500 KB Output is correct
16 Correct 144 ms 340 KB Output is correct
17 Correct 146 ms 552 KB Output is correct
18 Correct 167 ms 552 KB Output is correct
19 Correct 190 ms 15828 KB Output is correct
20 Correct 309 ms 43584 KB Output is correct
21 Correct 149 ms 3028 KB Output is correct
22 Correct 149 ms 1620 KB Output is correct
23 Correct 375 ms 53912 KB Output is correct
24 Correct 556 ms 86044 KB Output is correct
25 Correct 550 ms 85232 KB Output is correct