oj.uz

Submission #789313

# Submission time Handle Problem Language Result Execution time Memory
789313 2023-07-21T09:08:38 Z ymm Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 43124 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

vector<int> shf(vector<int> vec)
{
	int n = vec.size();
	vector<int> ans;
	int p0 = 0, p1 = n/2;
	Loop (_,0,n) {
		if (p1 == n || (p0 < n/2 && vec[p0] < vec[p1]))
			ans.push_back(vec[p0++]);
		else
			ans.push_back(vec[p1++]);
	}
	return ans;
}

const int N = 1'000'010;
int ans[N];
vector<pii> Q[N];

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	vector<int> vec(n);
	//iota(vec.begin(), vec.end(), 0);
	//auto pleh = vec;
	//int cntt = 0;
	//for (;;) {
	//	int cnt = 0;
	//	vec = pleh;
	//	for (;;) {
	//		auto tmp = shf(vec);
	//		if (tmp == vec)
	//			break;
	//		vec = tmp;
	//		++cnt;
	//	}
	//	cntt = max(cntt, cnt);
	//	if (!next_permutation(pleh.begin(), pleh.end()))
	//		break;
	//}
	//cout << cntt << '\n';
	//return 0;
	//mt19937_64 rd(chrono::high_resolution_clock::now().time_since_epoch().count());
	//iota(vec.begin(), vec.end(), 0);
	//shuffle(vec.begin(), vec.end(), rd);
	for (int &x : vec)
		cin >> x;
	//vecs.push_back(vec);
	Loop (i,0,q) {
		int t, p;
		cin >> t >> p;
		--p;
		t = min(t, n);
		Q[t].push_back({p, i});
	}
	int p0 = 0, p1 = n;
	vector<int> vec2(n);
	Loop (i,0,n) {
		for (auto [p, j] : Q[i])
			ans[j] = vec[p];
		merge(vec.data()+p0, vec.data()+n/2, vec.data()+n/2, vec.data()+p1, vec2.data()+p0);//vec = shf(vec);
		vec.swap(vec2);
		//while (p0 < n/2 && vec[p0] == vec2[p0])
		//	++p0;
		//while (n/2 < p1 && vec[p1-1] == vec2[p1-1])
		//	--p1;
		//vec = shf(vec);
	}
	for (auto [p, j] : Q[n])
		ans[j] = vec[p];
	Loop (i,0,q)
		cout << ans[i] << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 41788 KB Output is correct
2 Correct 161 ms 40896 KB Output is correct
3 Correct 156 ms 40404 KB Output is correct
4 Correct 167 ms 40108 KB Output is correct
5 Correct 172 ms 42736 KB Output is correct
6 Correct 155 ms 42872 KB Output is correct
7 Correct 163 ms 43124 KB Output is correct
8 Correct 158 ms 41496 KB Output is correct
9 Correct 152 ms 40600 KB Output is correct
10 Correct 155 ms 40256 KB Output is correct
11 Correct 156 ms 40748 KB Output is correct
12 Correct 150 ms 38872 KB Output is correct
13 Correct 162 ms 39636 KB Output is correct
14 Correct 172 ms 41756 KB Output is correct
15 Correct 158 ms 40076 KB Output is correct
16 Correct 14 ms 23764 KB Output is correct
17 Correct 154 ms 39064 KB Output is correct
18 Correct 155 ms 38848 KB Output is correct
19 Correct 13 ms 23728 KB Output is correct
20 Correct 13 ms 23724 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3042 ms 33100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3038 ms 26984 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 41788 KB Output is correct
2 Correct 161 ms 40896 KB Output is correct
3 Correct 156 ms 40404 KB Output is correct
4 Correct 167 ms 40108 KB Output is correct
5 Correct 172 ms 42736 KB Output is correct
6 Correct 155 ms 42872 KB Output is correct
7 Correct 163 ms 43124 KB Output is correct
8 Correct 158 ms 41496 KB Output is correct
9 Correct 152 ms 40600 KB Output is correct
10 Correct 155 ms 40256 KB Output is correct
11 Correct 156 ms 40748 KB Output is correct
12 Correct 150 ms 38872 KB Output is correct
13 Correct 162 ms 39636 KB Output is correct
14 Correct 172 ms 41756 KB Output is correct
15 Correct 158 ms 40076 KB Output is correct
16 Correct 14 ms 23764 KB Output is correct
17 Correct 154 ms 39064 KB Output is correct
18 Correct 155 ms 38848 KB Output is correct
19 Correct 13 ms 23728 KB Output is correct
20 Correct 13 ms 23724 KB Output is correct
21 Execution timed out 3042 ms 33100 KB Time limit exceeded
22 Halted 0 ms 0 KB -