제출 #361000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
361000		amunduzbaev	Permutation Recovery (info1cup17_permutation)	C++14	0 / 100	1 ms	384 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 
typedef vector<ll> vll;
typedef vector<int> vii;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
 
const int N = 1e3+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);

#define MULTI 0

int n, m, s, k, ans, a[N];
int used[N], res[N], dp[N], par[N];
int edges[N][N], sz[N];

void solve(int t_case){
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=n-1;i>=1;i--) a[i] -= a[i-1];
	//a[0] = 1;
	for(int i=1;i<n;i++){
		// we should find things such that their sum is a[i] in range 0 -> i-1
		memset(dp, 0, sizeof dp);
		memset(par, -1, sizeof par);
		dp[0] = 1; //, par[0] = -1;
		int gg = a[i]-1;
		for(int j=i-1;j>=0;j--){
			for(int tt = gg; tt >= a[j]; tt--){
				if(dp[tt]) continue;
				if(dp[tt - a[j]]){
					dp[tt] = 1;
					par[tt] = j;
				}
			}
		}
		
		//cout<<gg<<"\n";
		//for(int i=0;i<=gg;i++) cout<<dp[i]<<" ";
		//cout<<"\n";
		//for(int i=0;i<=gg;i++) cout<<par[i]<<" ";
		//cout<<"\n";
		
		int tt = gg;
		while(par[tt] != -1){
			edges[par[tt]][i] = 1;
			sz[par[tt]]++;
			tt = tt - a[par[tt]];
		}
	}
	
	
	//cout<<"\n";
	//for(int i=0;i<n;i++){
		//for(int j=0;j<n;j++){
			//cout<<edges[i][j]<<" ";
		//}cout<<"\n";
	//}
	
	set<pii> ss;
	for(int i=0;i<n;i++) ss.insert({sz[i], i});
	
	//for(auto x:ss) cout<<x.ff<<" "<<x.ss<<"\n";
	//cout<<"\n";
	
	int last = n;
	for(int i=0;i<n;i++){
		auto cur = ss.begin();
		int in = (*cur).ss;
		res[in] = last--;
		for(int i=0;i<n;i++){
			if(edges[i][in]){
				edges[i][in] = 0;
				ss.erase({sz[i], i});
				sz[i]--;
				ss.insert({sz[i], i});
			}
		}
		ss.erase(cur);
	}
	
	for(int i=0;i<n;i++) cout<<res[i]<<" ";
	cout<<"\n";
}

signed main(){
	NeedForSpeed
		
	if(!MULTI){
		solve(1);
	} else{
		int t;
		cin>>t;
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	}
	return 0;
}

• Subtask 1: 0 / 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