| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 644531 | loggerr | Permutation Recovery (info1cup17_permutation) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
D - 60
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include "bits/stdc++.h"
using namespace std;
using ll = __int128_t;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ld = long double;
using str = string;
const ld eps = 1e-8;
#define int long long
#define vc vector
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define ff first
#define ss second
#define pb push_back
#define forn(id, num) for (int id = 0; id < num; ++id)
#define sz(arr) (int)arr.size()
#ifdef LOCAL
#define debug(x) cerr << #x << ": " << x << endl;
#else
#define debug(x)
#endif
template<typename T, typename Y>
istream& operator>>(istream &other, std::pair<T, Y> &v_) {
other >> v_.first >> v_.second; return other;
}
template<typename T, typename Y>
ostream& operator<<(ostream &other, const std::pair<T, Y> v_) {
other << v_.first << ' ' << v_.second; return other;
}
template<typename T>
istream& operator>>(istream &other, vector<T> &v_) {
for (T &x : v_) other >> x; return other;
}
template<typename T>
ostream& operator<<(ostream &other, const vector<T> v_) {
for (T &x : v_) other << x << ' '; return other;
}
template<typename T>
bool inmin(T& _x, T _y) {return _y < _x ? (_x = _y, true) : false;}
template<typename T>
bool inmax(T& _x, T _y) {return _y > _x ? (_x = _y, true) : false;}
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline void solve();
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
freopen("/Users/alexsus/Desktop/solve/read.txt", "r", stdin);
#else
#endif
//cout << fixed << setprecision(10);
ll tt;
tt = 1;
//cin >> tt;
for (int i = 0; i < tt; ++i) {
solve();
}
return 0;
}
const ll Mod = 1e9 + 7;
class big_integer {
// основание системы счисления (1 000 000 000)
static const int BASE = 1e18;
// внутреннее хранилище числа
std::vector<int> _digits;
// знак числа
bool _is_negative;
void _remove_leading_zeros();
void _shift_right();
public:
// класс-исключение, бросаемое при делении на ноль
class divide_by_zero: public std::exception { };
big_integer();
big_integer(std::string);
big_integer(signed char);
big_integer(unsigned char);
big_integer(signed short);
big_integer(unsigned short);
big_integer(signed int);
big_integer(unsigned int);
big_integer(signed long);
big_integer(unsigned long);
big_integer(signed long long);
big_integer(unsigned long long);
friend std::ostream& operator <<(std::ostream&, const big_integer&);
operator std::string() const;
const big_integer operator +() const;
const big_integer operator -() const;
const big_integer operator ++();
const big_integer operator ++(int);
const big_integer operator --();
const big_integer operator --(int);
friend bool operator ==(const big_integer&, const big_integer&);
friend bool operator <(const big_integer&, const big_integer&);
friend bool operator !=(const big_integer&, const big_integer&);
friend bool operator <=(const big_integer&, const big_integer&);
friend bool operator >(const big_integer&, const big_integer&);
friend bool operator >=(const big_integer&, const big_integer&);
friend const big_integer operator +(big_integer, const big_integer&);
big_integer& operator +=(const big_integer&);
friend const big_integer operator -(big_integer, const big_integer&);
big_integer& operator -=(const big_integer&);
friend const big_integer operator *(const big_integer&, const big_integer&);
big_integer& operator *=(const big_integer&);
friend const big_integer operator /(const big_integer&, const big_integer&);
big_integer& operator /=(const big_integer&);
friend const big_integer operator %(const big_integer&, const big_integer&);
big_integer& operator %=(const big_integer&);
bool odd() const;
bool even() const;
const big_integer pow(big_integer) const;
};
// создает длинное целое число со значением 0
big_integer::big_integer() {
this->_is_negative = false;
}
// создает длинное целое число из C++-строки
big_integer::big_integer(std::string str) {
if (str.length() == 0) {
this->_is_negative = false;
}
else {
if (str[0] == '-') {
str = str.substr(1);
this->_is_negative = true;
}
else {
this->_is_negative = false;
}
for (long long i = str.length(); i > 0; i -= 9) {
if (i < 9)
this->_digits.push_back(atoi(str.substr(0, i).c_str()));
else
this->_digits.push_back(atoi(str.substr(i - 9, 9).c_str()));
}
this->_remove_leading_zeros();
}
}
// удаляет ведущие нули
void big_integer::_remove_leading_zeros() {
while (this->_digits.size() > 1 && this->_digits.back() == 0) {
this->_digits.pop_back();
}
if (this->_digits.size() == 1 && this->_digits[0] == 0) this->_is_negative = false;
}
// печатает число в поток вывода
std::ostream& operator <<(std::ostream& os, const big_integer& bi) {
if (bi._digits.empty()) os << 0;
else {
if (bi._is_negative) os << '-';
os << bi._digits.back();
char old_fill = os.fill('0');
for (long long i = static_cast<long long>(bi._digits.size()) - 2; i >= 0; --i) os << std::setw(9) << bi._digits[i];
os.fill(old_fill);
}
return os;
}
// сравнивает два числа на равенство
bool operator ==(const big_integer& left, const big_integer& right) {
if (left._is_negative != right._is_negative) return false;
if (left._digits.empty()) {
if (right._digits.empty() || (right._digits.size() == 1 && right._digits[0] == 0)) return true;
else return false;
}
if (right._digits.empty()) {
if (left._digits.size() == 1 && left._digits[0] == 0) return true;
else return false;
}
if (left._digits.size() != right._digits.size()) return false;
for (size_t i = 0; i < left._digits.size(); ++i) if (left._digits[i] != right._digits[i]) return false;
return true;
}
// возвращает копию переданного числа
const big_integer big_integer::operator +() const {
return big_integer(*this);
}
// возвращает переданное число с другим знаком
const big_integer big_integer::operator -() const {
big_integer copy(*this);
copy._is_negative = !copy._is_negative;
return copy;
}
// проверяет, является ли левый операнд меньше правого
bool operator <(const big_integer& left, const big_integer& right) {
if (left == right) return false;
if (left._is_negative) {
if (right._is_negative) return ((-right) < (-left));
else return true;
}
else if (right._is_negative) return false;
else {
if (left._digits.size() != right._digits.size()) {
return left._digits.size() < right._digits.size();
}
else {
for (long long i = left._digits.size() - 1; i >= 0; --i) {
if (left._digits[i] != right._digits[i]) return left._digits[i] < right._digits[i];
}
return false;
}
}
}
// сравнивает два числа на неравенство
bool operator !=(const big_integer& left, const big_integer& right) {
return !(left == right);
}
// проверяет, является ли левый операнд меньше либо равен правого
bool operator <=(const big_integer& left, const big_integer& right) {
return (left < right || left == right);
}
// проверяет, является ли левый операнд больше правого
bool operator >(const big_integer& left, const big_integer& right) {
return !(left <= right);
}
// проверяет, является ли левый операнд больше либо равен правого
bool operator >=(const big_integer& left, const big_integer& right) {
return !(left < right);
}
// складывает два числа
const big_integer operator +(big_integer left, const big_integer& right) {
if (left._is_negative) {
if (right._is_negative) return -(-left + (-right));
else return right - (-left);
}
else if (right._is_negative) return left - (-right);
int carry = 0;
for (size_t i = 0; i < std::max(left._digits.size(), right._digits.size()) || carry != 0; ++i) {
if (i == left._digits.size()) left._digits.push_back(0);
left._digits[i] += carry + (i < right._digits.size() ? right._digits[i] : 0);
carry = left._digits[i] >= big_integer::BASE;
if (carry != 0) left._digits[i] -= big_integer::BASE;
}
return left;
}
// прибавляет к текущему числу новое
big_integer& big_integer::operator +=(const big_integer& value) {
return *this = (*this + value);
}
// префиксный инкремент
const big_integer big_integer::operator++() {
return (*this += 1);
}
// преобразует число к строке
big_integer::operator std::string() const {
std::stringstream ss;
ss << *this;
return ss.str();
}
// преобразует signed char к big_integer
big_integer::big_integer(signed char c) {
if (c < 0) this->_is_negative = true;
else this->_is_negative = false;
this->_digits.push_back(std::abs(c));
}
// преобразует unsigned char к big_integer
big_integer::big_integer(unsigned char c) {
this->_is_negative = false;
this->_digits.push_back(c);
}
// преобразует signed short к big_integer
big_integer::big_integer(signed short s) {
if (s < 0) this->_is_negative = true;
else this->_is_negative = false;
this->_digits.push_back(std::abs(s));
}
// преобразует unsigned short к big_integer
big_integer::big_integer(unsigned short s) {
this->_is_negative = false;
this->_digits.push_back(s);
}
// преобразует signed int к big_integer
big_integer::big_integer(signed int i) {
if (i < 0) this->_is_negative = true;
else this->_is_negative = false;
this->_digits.push_back(std::abs(i) % big_integer::BASE);
i /= big_integer::BASE;
if (i != 0) this->_digits.push_back(std::abs(i));
}
// преобразует unsigned int к big_integer
big_integer::big_integer(unsigned int i) {
this->_digits.push_back(i % big_integer::BASE);
i /= big_integer::BASE;
if (i != 0) this->_digits.push_back(i);
}
// преобразует signed long к big_integer
big_integer::big_integer(signed long l) {
if (l < 0) this->_is_negative = true;
else this->_is_negative = false;
this->_digits.push_back(std::abs(l) % big_integer::BASE);
l /= big_integer::BASE;
if (l != 0) this->_digits.push_back(std::abs(l));
}
// преобразует unsigned long к big_integer
big_integer::big_integer(unsigned long l) {
this->_digits.push_back(l % big_integer::BASE);
l /= big_integer::BASE;
if (l != 0) this->_digits.push_back(l);
}
// преобразует signed long long к big_integer
big_integer::big_integer(signed long long l) {
if (l < 0) { this->_is_negative = true; l = -l; }
else this->_is_negative = false;
do {
this->_digits.push_back(l % big_integer::BASE);
l /= big_integer::BASE;
} while (l != 0);
}
// преобразует unsigned long long к big_integer
big_integer::big_integer(unsigned long long l) {
this->_is_negative = false;
do {
this->_digits.push_back(l % big_integer::BASE);
l /= big_integer::BASE;
} while (l != 0);
}
// постфиксный инкремент
const big_integer big_integer::operator ++(int) {
*this += 1;
return *this - 1;
}
// префиксный декремент
const big_integer big_integer::operator --() {
return *this -= 1;
}
// постфиксный декремент
const big_integer big_integer::operator --(int) {
*this -= 1;
return *this + 1;
}
// вычитает два числа
const big_integer operator -(big_integer left, const big_integer& right) {
if (right._is_negative) return left + (-right);
else if (left._is_negative) return -(-left + right);
else if (left < right) return -(right - left);
int carry = 0;
for (size_t i = 0; i < right._digits.size() || carry != 0; ++i) {
left._digits[i] -= carry + (i < right._digits.size() ? right._digits[i] : 0);
carry = left._digits[i] < 0;
if (carry != 0) left._digits[i] += big_integer::BASE;
}
left._remove_leading_zeros();
return left;
}
// вычитает из текущего числа новое
big_integer& big_integer::operator -=(const big_integer& value) {
return *this = (*this - value);
}
// перемножает два числа
const big_integer operator *(const big_integer& left, const big_integer& right) {
big_integer result;
result._digits.resize(left._digits.size() + right._digits.size());
for (size_t i = 0; i < left._digits.size(); ++i) {
int carry = 0;
for (size_t j = 0; j < right._digits.size() || carry != 0; ++j) {
long long cur = result._digits[i + j] +
left._digits[i] * 1LL * (j < right._digits.size() ? right._digits[j] : 0) + carry;
result._digits[i + j] = static_cast<int>(cur % big_integer::BASE);
carry = static_cast<int>(cur / big_integer::BASE);
}
}
result._is_negative = left._is_negative != right._is_negative;
result._remove_leading_zeros();
return result;
}
// домножает текущее число на указанное
big_integer& big_integer::operator *=(const big_integer& value) {
return *this = (*this * value);
}
// сдвигает все разряды на 1 вправо (домножает на BASE)
void big_integer::_shift_right() {
if (this->_digits.size() == 0) {
this->_digits.push_back(0);
return;
}
this->_digits.push_back(this->_digits[this->_digits.size() - 1]);
for (size_t i = this->_digits.size() - 2; i > 0; --i) this->_digits[i] = this->_digits[i - 1];
this->_digits[0] = 0;
}
// делит два числа
const big_integer operator /(const big_integer& left, const big_integer& right) {
if (right == 0) throw big_integer::divide_by_zero();
big_integer b = right;
b._is_negative = false;
big_integer result, current;
result._digits.resize(left._digits.size());
for (long long i = static_cast<long long>(left._digits.size()) - 1; i >= 0; --i) {
current._shift_right();
current._digits[0] = left._digits[i];
current._remove_leading_zeros();
int x = 0, l = 0, r = big_integer::BASE;
while (l <= r) {
int m = (l + r) / 2;
big_integer t = b * m;
if (t <= current) {
x = m;
l = m + 1;
}
else r = m - 1;
}
result._digits[i] = x;
current = current - b * x;
}
result._is_negative = left._is_negative != right._is_negative;
result._remove_leading_zeros();
return result;
}
// делит текущее число на указанное
big_integer& big_integer::operator /=(const big_integer& value) {
return *this = (*this / value);
}
// возвращает остаток от деления двух чисел
const big_integer operator %(const big_integer& left, const big_integer& right) {
big_integer result = left - (left / right) * right;
if (result._is_negative) result += right;
return result;
}
// присваивает текущему числу остаток от деления на другое число
big_integer& big_integer::operator %=(const big_integer& value) {
return *this = (*this % value);
}
// проверяет, является ли текущее число нечетным
bool big_integer::odd() const {
if (this->_digits.size() == 0) return false;
return this->_digits[0] & 1;
}
// проверяет, является ли текущее число четным
bool big_integer::even() const {
return !this->odd();
}
// возводит текущее число в указанную степень
const big_integer big_integer::pow(big_integer n) const {
big_integer a(*this), result(1);
while (n != 0) {
if (n.odd()) result *= a;
a *= a;
n /= 2;
}
return result;
}
struct node {
node *l, *r;
ll y;
int id, c;
big_integer val, sm;
node (int _id, big_integer _val) {
y = rnd() % Mod;
l = r = nullptr;
c = 1;
id = _id, val = _val, sm = _val;
}
};
int get_c(node *x) {
if (x == nullptr) return 0;
return x->c;
}
big_integer get_sm(node *x) {
if (x == nullptr) return 0;
return x->sm;
}
void upd(node * x) {
if (x == nullptr) return;
x->c = 1 + get_c(x->l) + get_c(x->r);
x->sm = x->val + get_sm(x->l) + get_sm(x->r);
}
int get_x(node *x) {
return get_c(x->l);
}
pair<node *, node *> split(node *t, int key) {
if (!t) return {nullptr, nullptr};
if (get_x(t) <= key) {
pair<node *, node *> res = split(t->r, key - get_x(t) - 1);
t->r = res.ff;
upd(t);
return {t, res.ss};
} else {
pair<node *, node *> res = split(t->l, key);
t->l = res.ss;
upd(t);
return {res.ff, t};
}
}
node *merge(node *tl, node *tr) {
if (!tl) return tr;
if (!tr) return tl;
if (tl->y >= tr->y) {
tl->r = merge(tl->r, tr);
upd(tl);
return tl;
} else {
tr->l = merge(tl, tr->l);
upd(tr);
return tr;
}
}
int find_order(node *t, big_integer value, int &pos) {
if (t == nullptr) return pos;
if (get_sm(t->l) + t->val < value) {
pos += get_c(t->l) + 1;
value -= get_sm(t->l) + t->val;
return find_order(t->r, value, pos);
} else {
return find_order(t->l, value, pos);
}
}
vector<int> p;
int last;
void order(node *t) {
if (t == nullptr) return;
order(t->l);
p[t->id] = last++;
order(t->r);
}
inline void solve() {
int n;
cin >> n;
vector<big_integer> pref(n);
forn(i, n) {
str s;
cin >> s;
pref[i] = big_integer(s);
}
vector<big_integer> dp(n);
dp[0] = pref[0];
for (int i = 1; i < n; ++i) {
dp[i] = pref[i] - pref[i - 1];
}
node *root = new node(0, dp[0]);
for (int i = 1; i < n; ++i) {
int pf = 0;
int pos = find_order(root, dp[i], pf);
node *next = new node(i, dp[i]);
auto [l, r] = split(root, pos - 1);
root = merge(l, merge(next, r));
}
last = 0;
p.resize(n);
order(root);
forn(i, n) {
cout << p[i] + 1 << ' ';
}
cout << '\n';
}