제출 #129371

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
129371		E869120	Permutation Recovery (info1cup17_permutation)	C++14	25 / 100	7 ms	508 KiB

Main

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 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