Submission #389346

#	Time	Username	Problem	Language	Result	Execution time	Memory
389346		abc864197532	Permutation Recovery (info1cup17_permutation)	C++17	43 / 100	4065 ms	69896 KiB

Main

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

struct BigInt {
    vector <int> val;
    BigInt(string s = "0") {
        for (int i = s.length() - 1; ~i; --i) {
            val.pb(s[i] - '0');
        }
    }
    BigInt operator - (const BigInt &o) const {
        vector <int> a = val;
        vector <int> result(a.size());
        for (int i = 0; i < o.val.size(); ++i) {
            if (a[i] >= o.val[i]) result[i] = a[i] - o.val[i];
            else result[i] = a[i] - o.val[i] + 10, a[i + 1]--;
        }
        for (int i = o.val.size(); i < a.size(); ++i) {
            result[i] = a[i];
        }
        while (result.size() > 1 && result.back() == 0) result.pop_back();
        BigInt ans;
        ans.val.pop_back();
        for (int i : result) ans.val.pb(i);
        return ans;
    }
    bool operator == (const BigInt &o) const {
        return val == o.val;
    }
};

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    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]);
    }
    vector <BigInt> cur = d;
    while (now <= n) {
        int i;
        for (i = n - 1; ~i; --i) {
            if (!p[i] && cur[i] == BigInt("1")) break;
        }
        p[i] = now++;
        for (int j = i + 1; j < n; ++j) if (!p[j]) {
            cur[j] = cur[j] - d[i];
        }
    }
    printv(p);
}

Compilation message (stderr)

permutation.cpp: In member function 'BigInt BigInt::operator-(const BigInt&) const':
permutation.cpp:30:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int i = 0; i < o.val.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~
permutation.cpp:34:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for (int i = o.val.size(); i < a.size(); ++i) {
      |                                    ~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 7
• Subtask 7: 0 / 16
• Subtask 8: 0 / 6