oj.uz

답안 #118805

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
118805 2019-06-19T20:13:51 Z Bruteforceman Permutation Recovery (info1cup17_permutation) C++11
10 / 100
 2 ms 384 KB 
#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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct

Subtask #6
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct

Subtask #8
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct