Submission #470155

#	Time	Username	Problem	Language	Result	Execution time	Memory
470155		radal	Watermelon (INOI20_watermelon)	C++14	0 / 100	12 ms	332 KiB

Main

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i = l; i < r; i++)
#define pb push_back
#define X first
#define Y second
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;

typedef long long ll;
typedef pair<int, int> pll;

const long long int mod = 1e9+7,N = 25;
int n,k;
int b[N],a[N],ind[N],ind2[N];
inline bool check(vector<int> ve){
    vector<pll> ve2,ve3;
    rep(i,0,n) ve2.pb({ve[i],i});
    int sz = n,p = 1;
    memset(a,-1,sizeof a);
    while (ve2.size()){
        rep(i,0,sz-1){
            if (ve2[i].X > ve2[i+1].X) ve3.pb(ve2[i]);
            else{
                a[ve2[i].Y] = p;
                if (b[ve2[i].Y] != a[ve2[i].Y]) return 0;
            }
        }
        ve3.pb(ve2[sz-1]);
        p++;
        if ((int)ve3.size() == sz) break;
        ve2 = ve3;
        sz = ve2.size();
        ve3.clear();
    }
    rep(i,0,n)
        if (a[i] != b[i]) return 0;
    return 1;
}
bool cmp(vector<int> ve,vector<int> ve2){
    rep(i,0,n){
        ind[ve[i]] = i;
        ind2[ve2[i]] = i;
    }
    rep(i,1,n+1) if (ind[i] < ind2[i]) return 1;
    return 0;
}
int main(){
    cin >> n >> k;
    assert((k < 3));
    rep(i,0,n) cin >> b[i];
    vector<vector<int>> ans;
    vector<int> ve;
    rep(i,1,n+1) ve.pb(i);
    if (check(ve)) ans.pb(ve);
    while (next_permutation(ve.begin(),ve.end()))
        if(check(ve)) ans.pb(ve);
    if ((int)ans.size() < k){
        cout << -1;
        return 0;
    }
    sort(ans.begin(),ans.end(),cmp);
    int sz = ans.size();
    rep(i,0,n) cout << ans[sz-k][i] << ' ';
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 18
• Subtask 5: 0 / 19