oj.uz

답안 #389504

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
389504 2021-04-14T06:51:37 Z abc864197532 Permutation Recovery (info1cup17_permutation) C++17
78 / 100
 4000 ms 594188 KB 
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define test(x) cout << #x << ' ' << x << endl
#define printv(x) { \
    for (auto a : x) cout << a << ' '; \
    cout << endl; \
}
#define pii pair<int, int>
#define pll pair<lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const int N = 512, abc = 864197532, K = 16;
const long long base = pow(10, K);

struct BigInt {
    vector <lli> val;
    BigInt(string s = "0") {
        int cnt = 0;
        lli pre = 0, pww = 1;
        for (int i = s.length() - 1; ~i; --i) {
            cnt++;
            pre += pww * (s[i] - '0');
            pww *= 10;
            if (cnt == K) val.pb(pre), cnt = pre = 0, pww = 1;
        }
        if (cnt) val.pb(pre);
    }
    BigInt operator - (const BigInt &o) const {
        vector <lli> result(max(val.size(), o.val.size()));
        for (int i = 0; i < result.size(); ++i) {
            lli a = i < val.size() ? val[i] : 0;
            lli b = i < o.val.size() ? o.val[i] : 0;
            result[i] = a - b;
        }
        for (int i = 0; i < result.size(); ++i) {
            if (result[i] < 0) {
                int add = (-result[i] + base - 1) / base;
                result[i + 1] -= add;
                result[i] += add * base;
            }
        }
        while (result.size() > 1 && result.back() == 0) result.pop_back();
        BigInt ans;
        ans.val.pop_back();
        for (lli i : result) ans.val.pb(i);
        return ans;
    }
    BigInt operator + (const BigInt &o) const {
        vector <lli> result(max(val.size(), o.val.size()));
        for (int i = 0; i < result.size(); ++i) {
            lli a = i < val.size() ? val[i] : 0;
            lli b = i < o.val.size() ? o.val[i] : 0;
            result[i] = a + b;
        }
        for (int i = 0; i < result.size(); ++i) {
            if (result[i] >= base && i == result.size() - 1) result.pb(0);
            result[i + 1] += result[i] / base;
            result[i] %= base;
        }
        while (result.size() > 1 && result.back() == 0) result.pop_back();
        BigInt ans;
        ans.val.pop_back();
        for (lli i : result) ans.val.pb(i);
        return ans;
    }
    bool operator == (const BigInt &o) const {
        return val == o.val;
    }
    bool operator < (const BigInt &o) const {
        if (val.size() != o.val.size()) return val.size() < o.val.size();
        for (int i = val.size() - 1; ~i; --i) if (val[i] != o.val[i]) {
            return val[i] < o.val[i];
        }
        return false;
    }
} INF, one = BigInt("1"), zero;

struct Seg {
    int l, r, m;
    BigInt mn, lz;
    Seg* ch[2];
    Seg (int _l, int _r, vector <BigInt> &a) : l(_l), r(_r), m(l + r >> 1) {
        if (r - l > 1) {
            ch[0] = new Seg(l, m, a);
            ch[1] = new Seg(m, r, a);
            pull();
        } else {
            mn = a[l];
        }
    }
    void pull() {
        if (ch[0]->mn < ch[1]->mn) mn = ch[0]->mn;
        else mn = ch[1]->mn;
    }
    void give(BigInt i) {
        lz = lz + i;
        mn = mn - i;
    }
    void push() {
        if (lz == zero) return;
        ch[0]->give(lz), ch[1]->give(lz);
        lz = zero;
    }
    void modify(int a, int b, BigInt v) {
        if (a <= l && r <= b) give(v);
        else {
            push();
            if (a < m) ch[0]->modify(a, b, v);
            if (m < b) ch[1]->modify(a, b, v);
            pull();
        }
    }
    int query() {
        if (r - l == 1) {
            mn = INF;
            return l;
        }
        push();
        int ans;
        if (ch[1]->mn == one) ans = ch[1]->query();
        else ans = ch[0]->query();
        pull();
        return ans;
    }
};

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    INF.val.pop_back();
    while (INF.val.size() < 275) INF.val.pb(base - 1);
    int n;
    cin >> n;
    vector <BigInt> a;
    string s;
    for (int i = 0; i < n; ++i) cin >> s, a.pb(BigInt(s));
    vector <BigInt> d(n);
    vector <int> p(n, 0);
    int now = 1;
    for (int i = 0; i < n; ++i) {
        d[i] = (i ? a[i] - a[i - 1] : a[i]);
    }
    Seg root(0, n, d);
    while (now <= n) {
        int i = root.query();
        p[i] = now++;
        root.modify(i, n, d[i]);
    }
    printv(p);
}

Compilation message

permutation.cpp: In member function 'BigInt BigInt::operator-(const BigInt&) const':
permutation.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int i = 0; i < result.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~
permutation.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             lli a = i < val.size() ? val[i] : 0;
      |                     ~~^~~~~~~~~~~~
permutation.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             lli b = i < o.val.size() ? o.val[i] : 0;
      |                     ~~^~~~~~~~~~~~~~
permutation.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int i = 0; i < result.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~
permutation.cpp: In member function 'BigInt BigInt::operator+(const BigInt&) const':
permutation.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = 0; i < result.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~
permutation.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             lli a = i < val.size() ? val[i] : 0;
      |                     ~~^~~~~~~~~~~~
permutation.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             lli b = i < o.val.size() ? o.val[i] : 0;
      |                     ~~^~~~~~~~~~~~~~
permutation.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (int i = 0; i < result.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~
permutation.cpp:62:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             if (result[i] >= base && i == result.size() - 1) result.pb(0);
      |                                      ~~^~~~~~~~~~~~~~~~~~~~
permutation.cpp: In constructor 'Seg::Seg(int, int, std::vector<BigInt>&)':
permutation.cpp:88:66: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |     Seg (int _l, int _r, vector <BigInt> &a) : l(_l), r(_r), m(l + r >> 1) {
      |                                                                ~~^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 3140 KB Output is correct
3 Correct 13 ms 5196 KB Output is correct
4 Correct 14 ms 5196 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 3140 KB Output is correct
3 Correct 13 ms 5196 KB Output is correct
4 Correct 14 ms 5196 KB Output is correct
5 Correct 1582 ms 302040 KB Output is correct

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 3140 KB Output is correct
3 Correct 13 ms 5196 KB Output is correct
4 Correct 14 ms 5196 KB Output is correct
5 Correct 1582 ms 302040 KB Output is correct
6 Correct 3039 ms 534212 KB Output is correct

Subtask #6
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 3140 KB Output is correct
3 Correct 13 ms 5196 KB Output is correct
4 Correct 14 ms 5196 KB Output is correct
5 Correct 1582 ms 302040 KB Output is correct
6 Correct 3039 ms 534212 KB Output is correct
7 Correct 3440 ms 553752 KB Output is correct

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 3140 KB Output is correct
3 Correct 13 ms 5196 KB Output is correct
4 Correct 14 ms 5196 KB Output is correct
5 Correct 1582 ms 302040 KB Output is correct
6 Correct 3039 ms 534212 KB Output is correct
7 Correct 3440 ms 553752 KB Output is correct
8 Correct 2732 ms 425288 KB Output is correct
9 Execution timed out 4083 ms 594188 KB Time limit exceeded

Subtask #8
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 3140 KB Output is correct
3 Correct 13 ms 5196 KB Output is correct
4 Correct 14 ms 5196 KB Output is correct
5 Correct 1582 ms 302040 KB Output is correct
6 Correct 3039 ms 534212 KB Output is correct
7 Correct 3440 ms 553752 KB Output is correct
8 Correct 2732 ms 425288 KB Output is correct
9 Execution timed out 4083 ms 594188 KB Time limit exceeded