oj.uz

답안 #993598

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
993598 2024-06-06T06:27:53 Z abczz 순열 (APIO22_perm) C++17
100 / 100
 25 ms 472 KB 
#include "perm.h"
#include <iostream>
#define ll long long

using namespace std;

vector <int> base2(ll k) {
	vector <int> V;
	ll mxbit = 0, cnt = 0;
	for (int i=59; i>=0; --i) {
		if (k & (1LL<<i)) {
			mxbit = i;
			break;
		}
	}
	for (int j=0; j<mxbit; ++j) {
		if (k & (1LL<<j)) V.push_back(-1);
		V.push_back(++cnt);
	}
	ll x = V.size();
	for (auto &u : V) {
		if (u == -1) u = x--;
		--u;
	}
	return V;
}

vector <int> base3(ll k) {
	vector <int> V, U;
	ll cnt = 0;
	ll tmp = k;
	while (tmp) {
		U.push_back(tmp % 3);
		tmp /= 3;
	}
	for (int i=0; i+1<U.size(); ++i) {
		if (U[i] == 1) V.push_back(-1);
		V.push_back(cnt+2);
		if (U[i] == 2) V.push_back(-1);
		V.push_back(cnt+1);
		cnt += 2;
	}
	if (U.back() == 2) V.push_back(++cnt);
	ll x = V.size();
	for (auto &u : V) {
		if (u == -1) u = x--;
		--u;
	}
	return V;
}

vector<int> opt(ll k) {
	auto b2 = base2(k);
	auto b3 = base3(k);
	if (b2.size() < b3.size()) return b2;
	else return b3;
}

std::vector<int> construct_permutation(long long k)
{
	auto f = opt(k);
	if (k <= 100) return f;
	for (int b=5; b<=100; ++b) {
		vector <int> pref = {};
		if (k % b != 0) pref = opt((k % b) + 1);
		vector<int> bin = opt(b);
		vector<int> nx = opt(k/b);
		for (auto &u : nx) {
			u += (ll)bin.size();
		}
		for (auto &u : pref) {
			u += (ll)(bin.size() + nx.size());
		}
		if (f.size() > pref.size() + bin.size() + nx.size()) {
			f.clear();
			for (auto u : pref) f.push_back(u);
			for (auto u : bin) f.push_back(u);
			for (auto u : nx) f.push_back(u);
		}
	}
	/*for (auto u : f) cout << u << " ";
	cout << endl;*/
	return f;
}

Compilation message

perm.cpp: In function 'std::vector<int> base3(long long int)':
perm.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for (int i=0; i+1<U.size(); ++i) {
      |                ~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #2
90.0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 11 ms 348 KB Output is correct
4 Correct 9 ms 348 KB Output is correct
5 Correct 15 ms 444 KB Output is correct
6 Correct 17 ms 348 KB Output is correct
7 Correct 25 ms 468 KB Output is correct
8 Correct 22 ms 344 KB Output is correct
9 Correct 23 ms 348 KB Output is correct
10 Correct 19 ms 348 KB Output is correct
11 Correct 21 ms 344 KB Output is correct
12 Correct 19 ms 472 KB Output is correct
13 Correct 21 ms 472 KB Output is correct