#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
