oj.uz

Submission #742281

# Submission time Handle Problem Language Result Execution time Memory
742281 2023-05-16T04:13:14 Z josanneo22 Rack (eJOI19_rack) C++17
40 / 100
 1000 ms 58124 KB 
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second 
#define int long long

vector<int> merge(vector<int>& a, vector<int>& b) {
	vector<int> ans; 
	vector<int> oda, odb, eva, evb;
	for (int i = 0; i < a.size(); i++) {
		if (a[i] % 2 == 1) oda.pb(a[i]);
		else eva.pb(a[i]);
	}
	for (int i = 0; i < b.size(); i++) {
		if (b[i] % 2 == 1) odb.pb(b[i]);
		else evb.pb(b[i]);
	}
	if (oda.size() == 1 && evb.size() == 1 && odb.size() == 0 && eva.size() == 0) {
		ans.push_back(oda[0]);
		ans.push_back(evb[0]);
		return ans;
	}
	int pt = 0, chance = 0;
	while (pt < oda.size()) {
		if (chance == 0 && oda.size() > pt) ans.pb(oda[pt]);
		else if (chance==1 && odb.size() > pt)ans.pb(odb[pt]);
		if (chance == 1) pt++;
		chance = 1 - chance;
	}
	pt = 0, chance = 0;
	while (pt < eva.size()) {
		if (chance == 0 && eva.size() > pt) ans.pb(eva[pt]);
		else if (chance == 1 && evb.size() > pt)ans.pb(evb[pt]);
		if (chance == 1) pt++;
		chance = 1 - chance;
	}
	return ans;
}
vector<int> call(int l, int r) { 
	if (l==r) return { l };
	else {
		int md = l + (r - l) / 2; 
		vector<int> a = call(l, md), b = call(md + 1, r); 
		return merge(a, b);
	}
}
void solve() {
	int n, k; cin >> n >> k;
	vector<int> ans = call(1, (1LL << n));
	cout << ans[k - 1] << '\n';
}
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	solve();
}

Compilation message

rack.cpp: In function 'std::vector<long long int> merge(std::vector<long long int>&, std::vector<long long int>&)':
rack.cpp:14:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for (int i = 0; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~
rack.cpp:18:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for (int i = 0; i < b.size(); i++) {
      |                  ~~^~~~~~~~~~
rack.cpp:28:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  while (pt < oda.size()) {
      |         ~~~^~~~~~~~~~~~
rack.cpp:29:33: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   29 |   if (chance == 0 && oda.size() > pt) ans.pb(oda[pt]);
      |                      ~~~~~~~~~~~^~~~
rack.cpp:30:36: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   30 |   else if (chance==1 && odb.size() > pt)ans.pb(odb[pt]);
      |                         ~~~~~~~~~~~^~~~
rack.cpp:35:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  while (pt < eva.size()) {
      |         ~~~^~~~~~~~~~~~
rack.cpp:36:33: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   36 |   if (chance == 0 && eva.size() > pt) ans.pb(eva[pt]);
      |                      ~~~~~~~~~~~^~~~
rack.cpp:37:38: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   37 |   else if (chance == 1 && evb.size() > pt)ans.pb(evb[pt]);
      |                           ~~~~~~~~~~~^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 25 ms 2108 KB Output is correct
9 Correct 134 ms 7436 KB Output is correct
10 Correct 462 ms 29112 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 25 ms 2108 KB Output is correct
9 Correct 134 ms 7436 KB Output is correct
10 Correct 462 ms 29112 KB Output is correct
11 Execution timed out 1037 ms 58124 KB Time limit exceeded
12 Halted 0 ms 0 KB -