Submission #118805

#	Time	Username	Problem	Language	Result	Execution time	Memory
118805		Bruteforceman	Permutation Recovery (info1cup17_permutation)	C++11	10 / 100	2 ms	384 KiB

Main

#include "bits/stdc++.h"
using namespace std;
int n;
int p[100010];
int q[100010];
int a[100010];

typedef pair <long long, int> pii;
const long long inf = 1e18;

pii t[100010 * 4];
int prop[100010 * 4];

void pushdown(int c) {
	int l = c << 1;
	int r = l + 1;
	t[l].first += prop[c];
	t[r].first += prop[c];
	prop[l] += prop[c];
	prop[r] += prop[c];
	prop[c] = 0;
}
void update(int x, int y, long long val, int c = 1, int b = 1, int e = n) {
	if(x <= b && e <= y) {
		t[c].first += val;
		prop[c] += val;
		return ;
	}
	if(y < b || e < x) return ;
	pushdown(c);
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	update(x, y, val, l, b, m);
	update(x, y, val, r, m + 1, e);
	t[c] = min(t[l], t[r]);
}
void build(int c = 1, int b = 1, int e = n) {
	if(b == e) {
		t[c].first = q[b];
		t[c].second = -b;
		return ;
	}
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	build(l, b, m);
	build(r, m + 1, e);
	t[c] = min(t[l], t[r]);
}

int main(int argc, char const *argv[])
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", p + i);
	}
	for(int i = n; i >= 1; i--) {
		p[i] -= p[i - 1];
	}
	for(int i = 1; i <= n; i++) {
		q[i] = p[i];
	}
	build();

	int cur = 0;
	for(int i = 1; i <= n; i++) {
		int idx = -t[1].second;
		update(idx, n, -q[idx]);
		update(idx, idx, inf);
		a[idx] = ++cur;
	}
	for(int i = 1; i <= n; i++) printf("%d ", a[i]);
	printf("\n");
	return 0;
}

Compilation message (stderr)

permutation.cpp: In function 'int main(int, const char**)':
permutation.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
permutation.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", p + i);
   ~~~~~^~~~~~~~~~~~~

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