제출 #389444

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
389444		8e7	Permutation Recovery (info1cup17_permutation)	C++14	25 / 100	1 ms	332 KiB

Main

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define ll long long
#define maxn 100005
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
#define pii pair<int, int>
using namespace std;
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
//template<lcass T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//find by order, order of key
ll q[maxn], b[maxn], c[maxn];
int a[maxn], found[maxn];
int main() {
	io
	int n;
	cin >> n;
	for (int i = 0;i < n;i++) cin >> q[i];
	ll tb = 0;
	for (int i = 0;i < n;i++) {
		b[i] = q[i] - (i ? q[i - 1] : 0);
		c[i] = tb + 1 - b[i];
		//cout << b[i] << " ";
		tb += b[i];
	}
	//cout << endl;
	for (int i = 0;i < n;i++) {
		for (int j = n - 1;j >= 0;j--) {
			if (found[j]) continue;
			if (c[j] == 0) {
				a[j] = n - i;
				found[j] = 1;
				for (int k = j + 1;k < n;k++) c[k] -= b[j];
				break;
			}
		}
	}
	for (int i = 0;i < n;i++) cout << a[i] << " ";
	cout << "\n";
}
/*
4
1 2 5 6

6
1 3 5 9 11 21
 */

• 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