답안 #644535

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
644535	2022-09-24T20:47:49 Z	loggerr	Permutation Recovery (info1cup17_permutation)	C++14	10 / 100	2 ms	456 KB

permutation

#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);
    
    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 ++();
    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 += 1ll);
}

// преобразует число к строке
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);
}


// вычитает два числа
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 == 0ll) 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();
}

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 0ll;
    return x->c;
}

big_integer get_sm(node *x) {
    if (x == nullptr) return 0ll;
    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';
}

Compilation message

permutation.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
permutation.cpp: In function 'std::istream& operator>>(std::istream&, std::vector<_Tp>&)':
permutation.cpp:42:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   42 |     for (T &x : v_) other >> x; return other;
      |     ^~~
permutation.cpp:42:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   42 |     for (T &x : v_) other >> x; return other;
      |                                 ^~~~~~
permutation.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<_Tp>)':
permutation.cpp:46:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   46 |     for (T &x : v_) other << x << ' '; return other;
      |     ^~~
permutation.cpp:46:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   46 |     for (T &x : v_) other << x << ' '; return other;
      |                                        ^~~~~~
permutation.cpp: In function 'void solve()':
permutation.cpp:567:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  567 |         auto [l, r] = split(root, pos - 1);
      |              ^

Subtask #1

10.0 / 10.0

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

Subtask #2

0 / 15.0

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

Subtask #3

0 / 18.0

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

Subtask #4

0 / 17.0

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

Subtask #5

0 / 11.0

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

Subtask #6

0 / 7.0

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

Subtask #7

0 / 16.0

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

Subtask #8

0 / 6.0

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