#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/*
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/
#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fs first
#define sc second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define endl '\n'
#define pii pair<int, int>
const int INF = 2000000005;
const ll BIG_INF = 2000000000000000005;
const int mod = 1000000007;
const int P = 31;
const ld PI = 3.141592653589793238462643;
const double eps = 1e-9;
using namespace std;
using namespace __gnu_pbds;
bool valid(int x, int y, int n, int m) {
return x >= 0 && y >= 0 && x < n && y < m;
}
mt19937 rng(1999999973);
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int osn = 1000000000;
class bigint {
bigint mult(bigint a, bigint b) {
vector<int> res(a.digits.size() + b.digits.size() + 5, 0);
for (int j = 0; j < b.digits.size(); j++) {
for (int i = 0; i < a.digits.size(); i++) {
res[i + j] += b.digits[j] * a.digits[i];
}
for (int i = 0; i < res.size(); i++) {
if (i == res.size() - 1) {
if (res[i] / osn > 0)
res.pb(0);
else
break;
}
res[i + 1] += res[i] / osn;
res[i] %= osn;
}
}
while(res.size() != 1 && res.back() == 0)
res.pop_back();
return bigint(res, a.neg ^ b.neg);
}
bigint sum(bigint a, bigint b) {
if (a.neg == b.neg) {
vector<int> res(max(a.digits.size(), b.digits.size()) + 5);
while(a.digits.size() < b.digits.size()) {
a.digits.pb(0);
}
while(b.digits.size() < a.digits.size()) {
b.digits.pb(0);
}
for (int i = 0; i < a.digits.size(); i++) {
res[i] = a.digits[i] + b.digits[i];
}
for (int i = 0; i < res.size(); i++) {
if (i == res.size() - 1) {
if (res[i] / osn > 0)
res.pb(0);
else
break;
}
res[i + 1] += res[i] / osn;
res[i] %= osn;
}
while(res.size() != 1 && res.back() == 0)
res.pop_back();
return bigint(res, a.neg);
}
if (a.neg == 0)
swap(a, b);
a.neg = 0;
if (a < b)
return subtract(b, a);
bigint res = subtract(a, b);
return bigint(res.digits, 1);
}
bigint subtract(bigint a, bigint b) {
if (a.neg == 0 && b.neg == 0) {
if (a < b) {
return bigint(subtract(b, a).digits, 1);
}
vector<int> res(max(a.digits.size(), b.digits.size()) + 5);
while(a.digits.size() < b.digits.size()) {
a.digits.pb(0);
}
while(b.digits.size() < a.digits.size()) {
b.digits.pb(0);
}
for (int i = 0; i < a.digits.size(); i++) {
res[i] = a.digits[i] - b.digits[i];
}
for (int i = 0; i < res.size(); i++) {
while(res[i] < 0) {
res[i] += osn;
res[i + 1]--;
}
}
while(res.size() != 1 && res.back() == 0)
res.pop_back();
return bigint(res);
}
return sum(a, bigint(b.digits, b.neg ^ 1));
}
public:
vector<int> digits;
int neg;
bigint(int x, int ng = 0) {
neg = ng;
if (x < 0) {
neg = 1;
x = -x;
}
if (x == 0) {
digits.pb(0);
return;
}
while(x > 0) {
digits.pb(x % osn);
x /= osn;
}
}
bigint(vector<int> d, int neg = 0) {
digits = d;
this->neg = neg;
}
bigint(){};
void operator += (const bigint other) {
bigint res = sum(bigint(this->digits, this->neg), other).digits;
this->digits = res.digits;
this->neg = res.neg;
}
bigint operator + (const bigint other) {
return sum(bigint(this->digits), other);
}
void operator *= (const bigint other) {
bigint res = mult(bigint(this->digits, this->neg), other).digits;
this->digits = res.digits;
this->neg = res.neg;
}
bigint operator * (const bigint other) {
return mult(bigint(this->digits), other);
}
void operator -= (const bigint other) {
bigint res = subtract(bigint(this->digits, this->neg), other).digits;
this->digits = res.digits;
this->neg = res.neg;
}
bigint operator - (const bigint other) {
return subtract(bigint(this->digits, this->neg), other);
}
bool operator != (const bigint other) const {
return digits != other.digits || (neg != other.neg && digits.back() != 0);
}
bool operator < (const bigint other) const {
if (neg != other.neg) {
return neg > other.neg;
}
if (digits.size() != other.digits.size())
return digits.size() < other.digits.size();
for (int i = digits.size() - 1; i >= 0; i--) {
if (digits[i] != other.digits[i])
return digits[i] < other.digits[i];
}
return false;
}
};
const int N = 70000 + 50;
bigint t[4 * N], pt[4 * N], q[N], ans[N], need[N];
bool del[N];
int p[N], n;
bigint cursum = bigint(1);
inline void push(int v, int tl, int tr) {
t[v] -= pt[v];
if (tl != tr) {
pt[v * 2] += pt[v];
pt[v * 2 + 1] += pt[v];
}
pt[v] = bigint(0);
}
void inc(int v, int tl, int tr, int l, int r, bigint x) {
push(v, tl, tr);
if (tl > r || tr < l)
return;
if (tl >= l && tr <= r) {
pt[v] += x;
push(v, tl, tr);
return;
}
int tm = (tl + tr) / 2;
inc(v * 2, tl, tm, l, r, x);
inc(v * 2 + 1, tm + 1, tr, l, r, x);
t[v] = bigint(-1);
if (t[v * 2].neg == 0 && (t[v * 2 + 1].neg == 1 || t[v * 2] < t[v * 2 + 1]))
t[v] = t[v * 2];
else
t[v] = t[v * 2 + 1];
}
int getPos(int v, int tl, int tr) {
push(v, tl, tr);
if (tl == tr) {
t[v] = bigint(-1);
return tl;
}
int tm = (tl + tr) / 2, ans;
push(v * 2, tl, tm);
push(v * 2 + 1, tm + 1, tr);
if (!(t[v * 2 + 1] != bigint(0)))
ans = getPos(v * 2 + 1, tm + 1, tr);
else
ans = getPos(v * 2, tl, tm);
t[v] = bigint(-1);
if (t[v * 2].neg == 0 && (t[v * 2 + 1].neg == 1 || t[v * 2] < t[v * 2 + 1]))
t[v] = t[v * 2];
else
t[v] = t[v * 2 + 1];
return ans;
}
void build(int v, int tl, int tr) {
if (tl == tr) {
t[v] = need[tl];
return;
}
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm + 1, tr);
if (t[v * 2] < t[v * 2 + 1])
t[v] = t[v * 2];
else
t[v] = t[v * 2 + 1];
}
signed main() {
fast_io;
cin >> n;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
int cur = 0;
vector<int> d;
for (int j = 0; j < s.size(); j++) {
if (j % 9 == 0) {
d.pb(cur);
cur = 0;
}
cur = cur * 10 + s[j] - '0';
}
d.pb(cur);
reverse(d.begin(), d.end());
q[i] = bigint(d);
}
ans[0] = q[0];
for (int i = 1; i < n; i++)
ans[i] = q[i] - q[i - 1];
for (int i = 0; i < n; i++) {
need[i] = cursum - ans[i];
cursum += ans[i];
}
build(1, 0, n - 1);
for (int i = n; i >= 1; i--) {
int pos = getPos(1, 0, n - 1);
p[pos] = i;
inc(1, 0, n - 1, pos, n - 1, ans[pos]);
}
for (int i = 0; i < n; i++)
cout << p[i] << " ";
return 0;
}
Compilation message
permutation.cpp: In member function 'bigint bigint::mult(bigint, bigint)':
permutation.cpp:48:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < b.digits.size(); j++) {
~~^~~~~~~~~~~~~~~~~
permutation.cpp:49:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a.digits.size(); i++) {
~~^~~~~~~~~~~~~~~~~
permutation.cpp:52:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < res.size(); i++) {
~~^~~~~~~~~~~~
permutation.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i == res.size() - 1) {
~~^~~~~~~~~~~~~~~~~
permutation.cpp: In member function 'bigint bigint::sum(bigint, bigint)':
permutation.cpp:78:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a.digits.size(); i++) {
~~^~~~~~~~~~~~~~~~~
permutation.cpp:81:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < res.size(); i++) {
~~^~~~~~~~~~~~
permutation.cpp:82:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i == res.size() - 1) {
~~^~~~~~~~~~~~~~~~~
permutation.cpp: In member function 'bigint bigint::subtract(bigint, bigint)':
permutation.cpp:117:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a.digits.size(); i++) {
~~^~~~~~~~~~~~~~~~~
permutation.cpp:120:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < res.size(); i++) {
~~^~~~~~~~~~~~
permutation.cpp: In function 'int main()':
permutation.cpp:287:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < s.size(); j++) {
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
24440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
24440 KB |
Output is correct |
| 2 |
Incorrect |
47 ms |
24568 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
24440 KB |
Output is correct |
| 2 |
Incorrect |
47 ms |
24568 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
24440 KB |
Output is correct |
| 2 |
Incorrect |
47 ms |
24568 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
24440 KB |
Output is correct |
| 2 |
Incorrect |
47 ms |
24568 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
24440 KB |
Output is correct |
| 2 |
Incorrect |
47 ms |
24568 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
24440 KB |
Output is correct |
| 2 |
Incorrect |
47 ms |
24568 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
24440 KB |
Output is correct |
| 2 |
Incorrect |
47 ms |
24568 KB |
Output isn't correct |
