This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
vector<int> mods = {(int) 1e9 + 7, 998244353, (int) 1e9 + 13};
struct Int {
vector<int> val;
Int(string s = "") {
for (auto& mod : mods) {
int ans = 0;
for (auto& c : s) {
ans = (ans * 10ll + c - '0') % mod;
}
val.push_back(ans);
}
}
Int& operator+=(const Int& other) {
for (int i = 0; i < (int) mods.size(); i++) {
val[i] = (val[i] + other.val[i]) % mods[i];
}
return *this;
}
Int& operator-=(const Int& other) {
for (int i = 0; i < (int) mods.size(); i++) {
val[i] -= other.val[i];
if (val[i] < 0) {
val[i] += mods[i];
}
}
return *this;
}
bool operator==(const Int& other) const {
return val == other.val;
}
};
void solve() {
int n;
cin >> n;
vector<Int> a(n);
for (int i = 0; i < n; i++) {
string s;
cin >> s;
a[i] = Int(s);
}
for (int i = n - 1; i; i--) {
a[i] -= a[i - 1];
}
vector<int> nxt(n, -1);
int root = 0;
for (int i = 1; i < n; i++) {
Int tmp("1");
if (a[i] == tmp) {
nxt[i] = root;
root = i;
continue;
}
int cur = root;
for (int j = 0; j < i; j++) {
tmp += a[cur];
if (tmp == a[i]) {
nxt[i] = nxt[cur];
nxt[cur] = i;
break;
}
cur = nxt[cur];
}
}
vector<int> ans(n);
for (int i = 0; i < n; i++) {
ans[root] = i;
root = nxt[root];
}
for (int i = 0; i < n; i++) {
cout << ans[i] + 1 << " ";
}
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
# | 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... |