oj.uz

답안 #129371

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
129371 2019-07-12T07:02:26 Z E869120 Permutation Recovery (info1cup17_permutation) C++14
25 / 100
 7 ms 508 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

const long long mod = 869120869120869120LL;
const long long mod2 = 133333333333333333LL;

class ModStarrySkyTree {
public:
	int size_ = 1;
	vector<pair<long long, int>> dat;
	vector<long long>lazy;

	void init(int sz, vector<long long> E) {
		while (size_ <= sz) size_ *= 2;
		dat.resize(size_ * 2, make_pair(mod, 0));
		lazy.resize(size_ * 2, 0LL);

		for (int i = 0; i < E.size(); i++) {
			int pos = (i + 1) + size_;
			dat[pos] = make_pair(E[i], -(i + 1));
			while (pos >= 2) {
				pos >>= 1;
				dat[pos] = min(dat[pos * 2], dat[pos * 2 + 1]);
			}
		}
	}
	void refresh(int pos) {
		if (pos < size_) {
			lazy[pos * 2 + 0] += lazy[pos]; lazy[pos * 2 + 0] %= mod;
			lazy[pos * 2 + 1] += lazy[pos]; lazy[pos * 2 + 1] %= mod;
			lazy[pos] = 0;
			pair<long long, int> cl = dat[pos * 2 + 0]; cl.first += lazy[pos * 2 + 0]; cl.first %= mod;
			pair<long long, int> cr = dat[pos * 2 + 1]; cr.first += lazy[pos * 2 + 1]; cr.first %= mod;
			dat[pos] = min(cl, cr);
		}
		else {
			dat[pos].first += lazy[pos]; dat[pos].first %= mod;
			lazy[pos] = 0;
		}
	}
	void add_(int l, int r, long long x, int a, int b, int u) {
		if (l <= a && b <= r) { lazy[u] += x; lazy[u] %= mod; refresh(u); return; }
		if (r <= a || b <= l) return;
		add_(l, r, x, a, (a + b) >> 1, u * 2 + 0);
		add_(l, r, x, (a + b) >> 1, b, u * 2 + 1);
		refresh(u);
	}
	void add(int l, int r, long long x) {
		x = (x + mod) % mod;
		add_(l, r, x, 0, size_, 1);
	}
	pair<long long, int> query_(int l, int r, int a, int b, int u) {
		refresh(u);
		if (l <= a && b <= r) return dat[u];
		if (r <= a || b <= l) return make_pair(mod, -1LL);

		pair<long long, int> cl = query_(l, r, a, (a + b) >> 1, u * 2 + 0);
		pair<long long, int> cr = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
		refresh(u);
		return min(cl, cr);
	}
	pair<long long, int> query(int l, int r) {
		return query_(l, r, 0, size_, 1);
	}
};

long long StringToMod(string S) {
	long long r = 0;
	for (int i = 0; i < S.size(); i++) {
		r *= 10LL; r += (long long)(S[i] - '0');
		r %= mod;
	}
	return r;
}

long long N, A[1 << 18], X[1 << 18]; vector<long long>F;
ModStarrySkyTree Z;

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		string V; cin >> V;
		A[i] = StringToMod(V);
	}
	for (int i = N; i >= 1; i--) A[i] = (A[i] - A[i - 1] + mod) % mod;
	for (int i = 1; i <= N; i++) F.push_back(A[i]);
	Z.init(N + 1, F);

	for (int i = 1; i <= N; i++) {
		pair<long long, int> G = Z.query(1, N + 1);
		int pos = -G.second;
		X[pos] = i;
		Z.add(pos + 1, N + 1, -A[pos]);
		Z.add(pos, pos + 1, mod2);
	}

	for (int i = 1; i <= N; i++) { if (i >= 2) cout << " "; cout << X[i]; } cout << endl;
	return 0;
}

Compilation message

permutation.cpp: In member function 'void ModStarrySkyTree::init(int, std::vector<long long int>)':
permutation.cpp:21:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < E.size(); i++) {
                   ~~^~~~~~~~~~
permutation.cpp: In function 'long long int StringToMod(std::__cxx11::string)':
permutation.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) {
                  ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Incorrect 7 ms 508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Incorrect 7 ms 508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Incorrect 7 ms 508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Incorrect 7 ms 508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Incorrect 7 ms 508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Incorrect 7 ms 508 KB Output isn't correct
4 Halted 0 ms 0 KB -