#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <string>
using namespace std;
#pragma warning (disable: 4996)
// ------------------ LIBRARY --------------------
const long long mod = 869120869120869120LL;
const long long mod2 = 777777777777777777LL;
const int BACKET = 80;
long long t[1 << 17], u[1 << 17], size_;
set<pair<long long, int>> Set[1 << 13];
void init(vector<long long>E) {
size_ = E.size() + 1;
for (int i = 1; i <= E.size(); i++) {
t[i] = E[i - 1];
Set[i / BACKET].insert(make_pair(t[i], i));
}
}
void add_range(int l, int r, long long x) {
int c = l / BACKET;
for (int i = l; i < r; i++) {
Set[c].erase(make_pair(t[i], i));
t[i] += x; if (t[i] >= mod) t[i] -= mod;
Set[c].insert(make_pair(t[i], i));
}
}
void add(int l, int r, long long x) {
x = (x + mod) % mod;
int c1 = l / BACKET, c2 = r / BACKET;
if (c1 == c2) add_range(l, r, x);
else {
add_range(l, (c1 + 1) * BACKET, x);
add_range(c2 * BACKET, r, x);
for (int i = c1 + 1; i < c2; i++) {
u[i] += x; if (u[i] >= mod) u[i] -= mod;
}
}
}
int get_minimum_id() {
int id = -1;
for (int i = size_ / BACKET; i >= 0; i--) {
long long T = (mod + 1LL - u[i]); if (T >= mod) T -= mod;
auto itr = Set[i].lower_bound(make_pair(T + 1LL, 0));
if (itr != Set[i].begin()) {
itr--;
if ((*itr).first == T) { id = (*itr).second; break; }
}
}
return id;
}
long long StringToMod(string S) {
long long r = 0;
for (int i = 0; i < S.size(); i++) {
r *= 10LL; r += (long long)(S[i] - '0');
r %= mod;
}
return r;
}
long long N, A[1 << 18], S[1 << 18];
vector<long long>F; char cc[1 << 18];
int main() {
cin >> N;
for (int i = 1; i <= N; i++) {
scanf("%s", &cc); string V = "";
for (int j = 0; j < 100000; j++) {
if (cc[j] == 0) break;
V += cc[j]; cc[j] = 0;
}
A[i] = StringToMod(V);
}
for (int i = N; i >= 1; i--) A[i] = (A[i] - A[i - 1] + mod) % mod;
for (int i = 1; i <= N; i++) F.push_back(A[i]);
init(F);
for (int i = 1; i <= N; i++) {
int pos1 = get_minimum_id();
S[pos1] = i;
add(pos1 + 1, N + 1, -A[pos1]);
add(pos1, pos1 + 1, mod2);
}
for (int i = 1; i <= N; i++) { if (i >= 2) printf(" "); printf("%d", S[i]); } printf("\n");
return 0;
}
Compilation message
permutation.cpp:7:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning (disable: 4996)
permutation.cpp: In function 'void init(std::vector<long long int>)':
permutation.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i <= E.size(); i++) {
~~^~~~~~~~~~~
permutation.cpp: In function 'long long int StringToMod(std::__cxx11::string)':
permutation.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < S.size(); i++) {
~~^~~~~~~~~~
permutation.cpp: In function 'int main()':
permutation.cpp:77:18: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[262144]' [-Wformat=]
scanf("%s", &cc); string V = "";
~~~^
permutation.cpp:95:75: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
for (int i = 1; i <= N; i++) { if (i >= 2) printf(" "); printf("%d", S[i]); } printf("\n");
~~~~^
permutation.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", &cc); string V = "";
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
764 KB |
Output is correct |
| 2 |
Correct |
7 ms |
764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
764 KB |
Output is correct |
| 2 |
Correct |
7 ms |
764 KB |
Output is correct |
| 3 |
Correct |
20 ms |
888 KB |
Output is correct |
| 4 |
Correct |
18 ms |
760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
764 KB |
Output is correct |
| 2 |
Correct |
7 ms |
764 KB |
Output is correct |
| 3 |
Correct |
20 ms |
888 KB |
Output is correct |
| 4 |
Correct |
18 ms |
760 KB |
Output is correct |
| 5 |
Correct |
1850 ms |
4688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
764 KB |
Output is correct |
| 2 |
Correct |
7 ms |
764 KB |
Output is correct |
| 3 |
Correct |
20 ms |
888 KB |
Output is correct |
| 4 |
Correct |
18 ms |
760 KB |
Output is correct |
| 5 |
Correct |
1850 ms |
4688 KB |
Output is correct |
| 6 |
Execution timed out |
4005 ms |
7304 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
764 KB |
Output is correct |
| 2 |
Correct |
7 ms |
764 KB |
Output is correct |
| 3 |
Correct |
20 ms |
888 KB |
Output is correct |
| 4 |
Correct |
18 ms |
760 KB |
Output is correct |
| 5 |
Correct |
1850 ms |
4688 KB |
Output is correct |
| 6 |
Execution timed out |
4005 ms |
7304 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
764 KB |
Output is correct |
| 2 |
Correct |
7 ms |
764 KB |
Output is correct |
| 3 |
Correct |
20 ms |
888 KB |
Output is correct |
| 4 |
Correct |
18 ms |
760 KB |
Output is correct |
| 5 |
Correct |
1850 ms |
4688 KB |
Output is correct |
| 6 |
Execution timed out |
4005 ms |
7304 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
764 KB |
Output is correct |
| 2 |
Correct |
7 ms |
764 KB |
Output is correct |
| 3 |
Correct |
20 ms |
888 KB |
Output is correct |
| 4 |
Correct |
18 ms |
760 KB |
Output is correct |
| 5 |
Correct |
1850 ms |
4688 KB |
Output is correct |
| 6 |
Execution timed out |
4005 ms |
7304 KB |
Time limit exceeded |
