oj.uz

Submission #349013

# Submission time Handle Problem Language Result Execution time Memory
349013 2021-01-16T10:29:37 Z RohamIzadidoost Permutation Recovery (info1cup17_permutation) C++14
10 / 100
 4000 ms 364 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 364 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 364 KB Output is correct
2 Execution timed out 4074 ms 364 KB Time limit exceeded

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 364 KB Output is correct
2 Execution timed out 4074 ms 364 KB Time limit exceeded

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 364 KB Output is correct
2 Execution timed out 4074 ms 364 KB Time limit exceeded

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 364 KB Output is correct
2 Execution timed out 4074 ms 364 KB Time limit exceeded

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 364 KB Output is correct
2 Execution timed out 4074 ms 364 KB Time limit exceeded

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 364 KB Output is correct
2 Execution timed out 4074 ms 364 KB Time limit exceeded

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 364 KB Output is correct
2 Execution timed out 4074 ms 364 KB Time limit exceeded