이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// #define _GLIBCXX_DEBUG
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#ifdef local
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define pary(a...) danb(#a, a)
#define debug(a...) qqbx(#a, a)
template <typename ...T> void qqbx(const char *s, T ...a) {
int cnt = sizeof...(T);
((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : ")\033[0m\n")));
}
template <typename T> void danb(const char *s, T L, T R) {
std::cerr << "\033[1;32m[ " << s << " ] = [ ";
for (int f = 0; L != R; ++L)
std::cerr << (f++ ? ", " : "") << *L;
std::cerr << " ]\033[0m\n";
}
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#define pary(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)
#define pb emplace_back
using namespace std;
using ll = int64_t;
const int maxn = 70025;
struct BigInteger : vector<int> {
static constexpr int base = 1000000000;
static constexpr int width = 9;
BigInteger() {}
explicit BigInteger(int x) : vector<int>{x} {}
friend istream & operator>>(istream &I, BigInteger &n) {
string s;
I >> s;
n.reserve(s.size() / 9);
reverse(s.begin(), s.end());
int cur = 0, cnt = 0, p = 1;
for (char c: s) {
cur = cur + (c - '0') * p;
if (++cnt == width) {
n.emplace_back(cur);
cur = 0;
cnt = 0;
p = 1;
} else {
p *= 10;
}
}
if (cnt)
n.emplace_back(cur);
return I;
}
BigInteger& operator+=(const BigInteger &rhs) {
if (size() < rhs.size()) resize(rhs.size());
int carry = 0;
for (size_t i = 0; i < size(); i++) {
at(i) += (i < rhs.size() ? rhs[i] : 0) + carry;
carry = at(i) / base;
at(i) %= base;
}
if (carry)
push_back(carry);
return *this;
}
BigInteger& operator-=(const BigInteger &rhs) {
int carry = 0;
for (size_t i = 0; i < size(); i++) {
at(i) -= (i < rhs.size() ? rhs[i] : 0) + carry;
if (at(i) < 0) {
at(i) += base;
carry = 1;
} else {
carry = 0;
}
}
while (!empty() && back() == 0) pop_back();
return *this;
}
};
using Int = BigInteger;
Int q[maxn];
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> q[i];
for (int i = n-1; i >= 1; i--)
q[i] -= q[i-1];
vector<int> ans{0};
for (int i = 1; i < n; i++) {
// pary(q[i].begin(), q[i].end());
if (q[i] == static_cast<Int>(1)) {
ans.insert(ans.begin(), i);
continue;
}
Int sum = static_cast<Int>(1);
for (int j = 0; j < i; j++) {
sum += q[ans[j]];
// pary(sum.begin(), sum.end());
if (sum == q[i]) {
ans.insert(ans.begin() + j + 1, i);
break;
}
}
}
vector<int> p(n);
for (int i = 0; i < n; i++)
p[ans[i]] = i+1;
for (int i = 0; i < n; i++)
cout << p[i] << (i+1==n ? '\n' : ' ');
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |