oj.uz

Submission #389454

# Submission time Handle Problem Language Result Execution time Memory
389454 2021-04-14T06:17:00 Z casperwang Permutation Recovery (info1cup17_permutation) C++14
25 / 100
 2 ms 332 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -