Submission #975693

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
975693	2024-05-05T18:02:22 Z	ShaShi	Permutation (APIO22_perm)	C++17	10 / 100	1000 ms	348 KB

perm

#include "perm.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define pii pair<int, int>



using namespace std;

typedef long long ll;


const int MAXN = (int)1e6 + 7;
const int LG = 60;



vector<int> solve1(ll k) {
	vector<int> res;

	bool flag = 0;

	for (int i=LG-1; i>=0; i--) {
		if (!(k&(1ll<<i))) continue;

		if (!flag) {
			for (int j=1; j<=i; j++) res.pb(j);
			flag = 1;

			continue;
		}

		for (int j=0; j<res.size(); j++) if (res[j] >= i+1) res[j]++;
		res.pb(i+1);
	}

	// for (int i=0; i<res.size(); i++) res[i]--;

	return res;
}


vector<int> solve2(ll k) {
	vector<int> res = solve1(k+1);

	if (k >= 2 && (k%2) == 0) {
		vector<int> res2 = solve2((k-2)/2);
		
		if (res2.size()+2 < res.size()) {
			int mx=1;
			for (int i=0; i<res2.size(); i++) mx = max(mx, ++res2[i]);

			res2.pb(mx+1); res2.pb(1);
			swap(res, res2);
		}
	}

	// if (k > 0) {
	// 	vector<int> res2 = solve2(k-1);

	// 	if (res2.size()+1 < res.size()) {
	// 		for (int i=0; i<res2.size(); i++) res2[i]++;

	// 		res2.pb(1);
	// 		swap(res, res2);
	// 	}
	// }

	if (k > 0 && (k%2) == 1) {
		vector<int> res2 = solve2((k-1)/2);

		if (res2.size()+1 < res.size()) {
			int mx = 0;
			for (int i=0; i<res2.size(); i++) mx = max(mx, res2[i]);

			res2.pb(mx+1);
			swap(res, res2);
		}
	}

	if (k >= 2 && ((k-2)%3) == 0) {
		vector<int> res2 = solve2((k-2)/3);

		if (res2.size()+2 < res.size()) {
			int mx = 0;
			for (int i=0; i<res2.size(); i++) mx = max(mx, res2[i]);

			res2.pb(mx+2); res2.pb(mx+1);
			swap(res, res2);
		}
	}


	if (k >= 3 && ((k-3)%4) == 0) {
		vector<int> res2 = solve2((k-3)/4);

		if (res2.size()+2 < res.size()) {
			int mx = 0;
			for (int i=0; i<res2.size(); i++) mx = max(mx, res2[i]);

			res2.pb(mx+1); res2.pb(mx+2);
			swap(res, res2);
		}
	}


	return res;
}


vector<int> construct_permutation(ll k) {
	// vector<int> res1 = solve1(k);

	// if (res1.size() <= 90) return res1;

	vector<int> res2 = solve2(k-1);
	for (int i=0; i<res2.size(); i++) res2[i]--;

	return res2;
}



// int main() {
// 	ll n = (1ll<<18);
// 	// ll n  = 511;
// 	vector<int> res = construct_permutation(n);

// 	cout << res.size() << endl;

// 	for (int i:res) cout << i << " ";


// 	return 0;
// }

Compilation message

perm.cpp: In function 'std::vector<int> solve1(ll)':
perm.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for (int j=0; j<res.size(); j++) if (res[j] >= i+1) res[j]++;
      |                 ~^~~~~~~~~~~
perm.cpp: In function 'std::vector<int> solve2(ll)':
perm.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    for (int i=0; i<res2.size(); i++) mx = max(mx, ++res2[i]);
      |                  ~^~~~~~~~~~~~
perm.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |    for (int i=0; i<res2.size(); i++) mx = max(mx, res2[i]);
      |                  ~^~~~~~~~~~~~
perm.cpp:90:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |    for (int i=0; i<res2.size(); i++) mx = max(mx, res2[i]);
      |                  ~^~~~~~~~~~~~
perm.cpp:103:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |    for (int i=0; i<res2.size(); i++) mx = max(mx, res2[i]);
      |                  ~^~~~~~~~~~~~
perm.cpp: In function 'std::vector<int> construct_permutation(ll)':
perm.cpp:121:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |  for (int i=0; i<res2.size(); i++) res2[i]--;
      |                ~^~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct

Subtask #2

0.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	8 ms	348 KB	Output is correct
4	Correct	42 ms	348 KB	Output is correct
5	Execution timed out	1059 ms	348 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-