oj.uz

Submission #958294

# Submission time Handle Problem Language Result Execution time Memory
958294 2024-04-05T10:23:23 Z pragmatist Permutation (APIO22_perm) C++17
100 / 100
 681 ms 692 KB 
#include "perm.h"
#include<bits/stdc++.h>
 
using namespace std;
 
long long dp[6000];
int a[6000];
int mn;
vector<int> ans;

void go(long long k, int n, int p[]) {
	for(int i = 1; i <= n; ++i) {
		a[i] = p[i-1];
	}
	long long cur = 1;
	for(int i = 1; i <= n; ++i) {
		dp[i] = 1;
		for(int j = 1; j < i; ++j) {
			if(a[j]<a[i]) {
				dp[i] += dp[j];
			}
		}
		cur += dp[i];
	}
	if(cur>k) {
		return;
	}
	int old = n;
	while(cur<k) {
		vector<pair<int, long long> > b;
		for(int i = 1; i <= n; ++i) {
			b.push_back({a[i], dp[i]});
		}
		sort(b.begin(), b.end());
		long long add = 1, need = k-cur;
		int nxt = 0;
		for(auto [x, y] : b) {
			if(add+y<=need) {
				nxt = x+1;
				add += y;								
			} else {
				break;
			}
		}
		for(int i = 0; i <= n; ++i) {
			if(a[i] >= nxt) {
				a[i]++;
			}
		}			
		a[++n] = nxt;
		dp[n] = add;
		cur += add;
	}
	assert(n<=200);
	vector<int> res;
	for(int i = 1; i <= n; ++i) {
		res.push_back(a[i]);
	}
	if(n<mn) {
		mn = n;
		ans = res;
	}
}

std::vector<int> construct_permutation(long long k) {
	srand(time(NULL));
	mn = 1e9;
	int p[6];
	int c = 1;
	for(int n = 1; n <= 5; ++n) {
		c *= n;
		for(int i = 0; i < n; ++i) {
			p[i] = i;
		} 
		for(int i = 1; i <= min(50, c); ++i) {
			random_shuffle(p, p+n);
			go(k, n, p);	
		}
	}                
    return ans;
}

Compilation message

perm.cpp: In function 'void go(long long int, int, int*)':
perm.cpp:28:6: warning: unused variable 'old' [-Wunused-variable]
   28 |  int old = n;
      |      ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 42 ms 344 KB Output is correct
4 Correct 63 ms 444 KB Output is correct
5 Correct 283 ms 440 KB Output is correct
6 Correct 278 ms 600 KB Output is correct
7 Correct 429 ms 344 KB Output is correct
8 Correct 633 ms 460 KB Output is correct
9 Correct 579 ms 692 KB Output is correct
10 Correct 681 ms 348 KB Output is correct
11 Correct 604 ms 452 KB Output is correct
12 Correct 513 ms 444 KB Output is correct
13 Correct 642 ms 448 KB Output is correct