Submission #389454

#	Time	Username	Problem	Language	Result	Execution time	Memory
389454		casperwang	Permutation Recovery (info1cup17_permutation)	C++14	25 / 100	2 ms	332 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define All(x) x.begin(), x.end()
#define pb emplace_back
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

const int MAXN = 70000;
int N;
int pre[MAXN+1];
int a[MAXN+1];
int ans[MAXN+1];
int sum[MAXN+1];
int ord[MAXN+1];

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> pre[i];
		a[i] = pre[i] - pre[i-1];
	}
	for (int i = 1; i <= N; i++) {
		int k = -1;
		for (int j = 0; j < i; j++) {
			if (a[i] == sum[j] + 1) {
				k = j + 1;
				break;
			}
		}
		for (int j = i; j > k; j--) {
			ans[j] = ans[j-1];
		}
		ans[k] = i;
		for (int j = k; j <= i; j++) {
			sum[j] = sum[j-1] + a[ans[j]];
		}
	}
	for (int i = 1; i <= N; i++) {
		ord[ans[i]] = i;
	}
	for (int i = 1; i <= N; i++) {
		cout << ord[i] << " \n"[i==N];
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 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