Submission #349013

#	Time	Username	Problem	Language	Result	Execution time	Memory
349013		RohamIzadidoost	Permutation Recovery (info1cup17_permutation)	C++14	10 / 100	4074 ms	364 KiB

Main

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)(x).size()
#define X   first
#define Y   second
#define mp  make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 1000*100+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
ll n  , dp[maxn] , ps[maxn] , a[maxn]; 
vec<int> v ; 
bool check(){
	dp[0] = 1 ; 
	for(int i = 1 ; i < sz(v) ; i ++ ){
		dp[i] = 1 ; 
		for(int j = i-1 ; j >= 0 ; j -- ){
			if(v[j] < v[i]) dp[i] += dp[j] ; 
		}
	}
	ps[0] = dp[0] ; 
	for(int i = 1 ; i < sz(v) ; i ++ ){
		ps[i] = ps[i-1] + dp[i] ; 
	}
	for(int i = 0 ; i < sz(v) ; i ++ ){
		if(ps[i] != a[i])return false; 
	}
	return true ;
}
int main()
{
	migmig ;
	cin>>n; 
	for(int i = 0 ; i < n ; i ++ ) cin>>a[i] ; 
	for(int i = 1 ;i <= n ;i  ++ ){
		v.pb(i) ; 
	}
	while(next_permutation(all(v))){
		if(check()){
			for(auto u : v) cout<<u <<" " ; 
			return 0 ; 
		}
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 18
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 7
• Subtask 7: 0 / 16
• Subtask 8: 0 / 6