#include <bits/extc++.h>
using namespace std;
//#define int long long
const int M = 1e9 + 9;
/** Fast input-output */
template <class T = int> inline T readInt();
inline double readDouble();
inline int readUInt();
inline int readChar(); // first non-blank character
inline void readWord( char *s );
inline bool readLine( char *s ); // do not save '\n'
inline bool isEof();
inline int getChar();
inline int peekChar();
inline bool seekEof();
inline void skipBlanks();
template <class T> inline void writeInt( T x, char end = 0, int len = -1 );
inline void writeChar( int x );
inline void writeWord( const char *s );
inline void writeDouble( double x, int len = 0 );
inline void flush();
static struct buffer_flusher_t {
~buffer_flusher_t() {
flush();
}
} buffer_flusher;
/** Read */
static const int buf_size = 4096;
static unsigned char buf[buf_size];
static int buf_len = 0, buf_pos = 0;
inline bool isEof() {
if (buf_pos == buf_len) {
buf_pos = 0, buf_len = fread(buf, 1, buf_size, stdin);
if (buf_pos == buf_len)
return 1;
}
return 0;
}
inline int getChar() {
return isEof() ? -1 : buf[buf_pos++];
}
inline int peekChar() {
return isEof() ? -1 : buf[buf_pos];
}
inline bool seekEof() {
int c;
while ((c = peekChar()) != -1 && c <= 32)
buf_pos++;
return c == -1;
}
inline void skipBlanks() {
while (!isEof() && buf[buf_pos] <= 32U)
buf_pos++;
}
inline int readChar() {
int c = getChar();
while (c != -1 && c <= 32)
c = getChar();
return c;
}
inline int readUInt() {
int c = readChar(), x = 0;
while ('0' <= c && c <= '9')
x = x * 10 + c - '0', c = getChar();
return x;
}
inline long long readInt() {
int s = 1, c = readChar();
long long x = 0;
if (c == '-')
s = -1, c = getChar();
else if (c == '+')
c = getChar();
while ('0' <= c && c <= '9')
x = (x * 10LL + (long long)c - (long long)'0') % M, c = getChar();
return s == 1 ? x : -x;
}
inline double readDouble() {
int s = 1, c = readChar();
double x = 0;
if (c == '-')
s = -1, c = getChar();
while ('0' <= c && c <= '9')
x = x * 10 + c - '0', c = getChar();
if (c == '.') {
c = getChar();
double coef = 1;
while ('0' <= c && c <= '9')
x += (c - '0') * (coef *= 1e-1), c = getChar();
}
return s == 1 ? x : -x;
}
inline void readWord( char *s ) {
int c = readChar();
while (c > 32)
*s++ = c, c = getChar();
*s = 0;
}
inline bool readLine( char *s ) {
int c = getChar();
while (c != '\n' && c != -1)
*s++ = c, c = getChar();
*s = 0;
return c != -1;
}
/** Write */
static int write_buf_pos = 0;
static char write_buf[buf_size];
inline void writeChar( int x ) {
if (write_buf_pos == buf_size)
fwrite(write_buf, 1, buf_size, stdout), write_buf_pos = 0;
write_buf[write_buf_pos++] = x;
}
inline void flush() {
if (write_buf_pos)
fwrite(write_buf, 1, write_buf_pos, stdout), write_buf_pos = 0;
}
template <class T>
inline void writeInt( T x, char end, int output_len ) {
if (x < 0)
writeChar('-'), x = -x;
char s[24];
int n = 0;
while (x || !n)
s[n++] = '0' + x % 10, x /= 10;
while (n < output_len)
s[n++] = '0';
while (n--)
writeChar(s[n]);
if (end)
writeChar(end);
}
inline void writeWord( const char *s ) {
while (*s)
writeChar(*s++);
}
inline void writeDouble( double x, int output_len ) {
if (x < 0)
writeChar('-'), x = -x;
int t = (int)x;
writeInt(t), x -= t;
writeChar('.');
for (int i = output_len - 1; i > 0; i--) {
x *= 10;
t = std::min((int)9, (int)x);
writeChar('0' + t), x -= t;
}
x *= 10;
t = std::min((int)9, (int)(x + 0.5));
writeChar('0' + t);
}
//#define int long long
using namespace __gnu_pbds;
struct Res {
const int K = 100;
struct Block {
vector<int> vec;
};
vector<int> get_val() {
vector<int> ans;
for (auto &c: blocks) {
for (auto c2: c.vec) {
ans.push_back(c2);
}
}
return ans;
}
vector<Block> blocks;
void build(vector<int> &vals) {
blocks.clear();
blocks.push_back({});
for (auto c: vals) {
if (blocks.back().vec.size() + 1 >= K) {
blocks.push_back({});
}
blocks.back().vec.push_back(c);
}
}
void rebuild() {
vector<int> vals = get_val();
build(vals);
}
void add(int ind, int el) {
for (int i = 0; i < blocks.size(); ++i) {
if (blocks[i].vec.size() >= ind) {
blocks[i].vec.insert(blocks[i].vec.begin() + ind, el);
if (blocks[i].vec.size() > 2 * K) {
rebuild();
}
return;
}
ind -= blocks[i].vec.size();
}
if (ind > 0) {
exit(1);
}
blocks.push_back({});
blocks.back().vec.push_back(el);
}
};
struct Zns {
const int K = 100;
struct Block {
vector<int> vec;
int summ = 0;
};
vector<int> get_val() {
vector<int> ans;
for (auto &c: blocks) {
for (auto c2: c.vec) {
ans.push_back(c2);
}
}
return ans;
}
vector<Block> blocks;
void build(vector<int> &vals) {
blocks.clear();
blocks.push_back({});
for (auto c: vals) {
if (blocks.back().vec.size() + 1 >= K) {
blocks.push_back({});
}
blocks.back().summ += c;
if (blocks.back().summ >= M) {
blocks.back().summ -= M;
}
blocks.back().vec.push_back(c);
}
}
void rebuild() {
vector<int> vals = get_val();
build(vals);
}
void add(int ind, int el) {
for (int i = 0; i < blocks.size(); ++i) {
if (blocks[i].vec.size() >= ind) {
blocks[i].vec.insert(blocks[i].vec.begin() + ind, el);
blocks[i].summ += el;
if (blocks[i].summ >= M) {
blocks[i].summ -= M;
}
if (blocks[i].vec.size() > 2 * K) {
rebuild();
}
return;
}
ind -= blocks[i].vec.size();
}
if (ind > 0) {
exit(1);
}
blocks.push_back({});
blocks.back().vec.push_back(el);
blocks.back().summ += el;
if (blocks.back().summ >= M) {
blocks.back().summ -= M;
}
}
int get_val(int ind) {
int ans = 0;
for (int i = 0; i < blocks.size(); ++i) {
if (ind < blocks[i].vec.size()) {
for (int j = 0; j < ind; ++j) {
ans += blocks[i].vec[j];
if (ans >= M) {
ans -= M;
}
}
ind = 0;
return ans;
} else {
ans += blocks[i].summ;
if (ans >= M) {
ans -= M;
}
ind -= blocks[i].vec.size();
}
}
return ans;
}
};
struct Vec {
const int K = 100;
struct Block {
vector<int> vec;
int summ = 0;
gp_hash_table<int, int> have;
};
vector<int> get_val() {
vector<int> ans;
for (auto &c: blocks) {
for (auto c2: c.vec) {
int el = (c2 + c.summ);
if (el >= M) {
el -= M;
}
ans.push_back(el);
}
}
return ans;
}
vector<Block> blocks;
void build(vector<int> &vals) {
blocks.clear();
blocks.push_back({});
for (auto c: vals) {
if (blocks.back().vec.size() + 1 >= K) {
blocks.push_back({});
}
blocks.back().have[c]++;
blocks.back().vec.push_back(c);
}
}
void rebuild() {
vector<int> vals = get_val();
build(vals);
}
void add(int ind, int el) {
for (int i = 0; i < blocks.size(); ++i) {
if (blocks[i].vec.size() >= ind) {
int newel = (el - blocks[i].summ + M);
if (newel >= M) {
newel -= M;
}
blocks[i].vec.insert(blocks[i].vec.begin() + ind, newel);
blocks[i].have[newel]++;
if (blocks[i].vec.size() > 2 * K) {
rebuild();
}
return;
}
ind -= blocks[i].vec.size();
}
if (ind > 0) {
exit(1);
}
blocks.push_back({});
int newel = (el - blocks.back().summ + M);
if (newel >= M) {
newel -= M;
}
blocks.back().vec.push_back(newel);
blocks.back().have[newel]++;
}
void add_val(int ind, int el) {
for (int i = 0; i < blocks.size(); ++i) {
if ((int) blocks[i].vec.size() <= ind) {
ind -= (int) blocks[i].vec.size();
} else if (ind <= 0) {
blocks[i].summ += el;
if (blocks[i].summ >= M) {
blocks[i].summ -= M;
}
} else {
for (auto &c: blocks[i].vec) {
if (ind <= 0) {
blocks[i].have[c]--;
c += el;
if (c >= M) {
c-= M;
}
blocks[i].have[c]++;
}
ind--;
}
}
}
}
int find_el(int el) {
int have = 0;
// rebuild();
for (int i = 0; i < blocks.size(); ++i) {
int nowel = el - blocks[i].summ;
nowel += M;
if (nowel >= M) {
nowel -= M;
}
if (blocks[i].have[nowel]) {
for (int j = 0; j < blocks[i].vec.size(); ++j) {
if (blocks[i].vec[j] == nowel) {
return have + j;
}
}
}
have += blocks[i].vec.size();
}
}
};
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.precision(37);
cout << fixed;
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
long long n = readInt();
int last = 0;
Res res;
Zns zns3;
Vec vec2;
for (int w = 0; w < n; ++w) {
long long a = readInt();
int zn = a - last + M;
if (zn >= M) {
zn -= M;
}
int ind = 0;
if (zn > 1) {
ind = 1 + vec2.find_el(zn - 1);
}
int pref = 0;
vec2.add_val(ind, zn);
pref = zns3.get_val(ind);
pref += zn;
if (pref >= M) {
pref -= M;
}
vec2.add(ind, pref);
zns3.add(ind, zn);
res.add(ind, w);
last = a;
}
vector<int> ans(n);
vector<int> vals = res.get_val();
for (int i = 0; i < n; ++i) {
ans[vals[i]] = i + 1;
}
for (auto c: ans) {
cout << c << " ";
}
return 0;
}
Compilation message
permutation.cpp: In member function 'void Res::build(std::vector<int>&)':
permutation.cpp:207:46: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
207 | if (blocks.back().vec.size() + 1 >= K) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
permutation.cpp: In member function 'void Res::add(int, int)':
permutation.cpp:222:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Res::Block>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
222 | for (int i = 0; i < blocks.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
permutation.cpp:223:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
223 | if (blocks[i].vec.size() >= ind) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~~~
permutation.cpp:227:42: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
227 | if (blocks[i].vec.size() > 2 * K) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~~~~
permutation.cpp: In member function 'void Zns::build(std::vector<int>&)':
permutation.cpp:269:46: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
269 | if (blocks.back().vec.size() + 1 >= K) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
permutation.cpp: In member function 'void Zns::add(int, int)':
permutation.cpp:288:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Zns::Block>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
288 | for (int i = 0; i < blocks.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
permutation.cpp:289:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
289 | if (blocks[i].vec.size() >= ind) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~~~
permutation.cpp:298:42: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
298 | if (blocks[i].vec.size() > 2 * K) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~~~~
permutation.cpp: In member function 'int Zns::get_val(int)':
permutation.cpp:320:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Zns::Block>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
320 | for (int i = 0; i < blocks.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
permutation.cpp:321:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
321 | if (ind < blocks[i].vec.size()) {
| ~~~~^~~~~~~~~~~~~~~~~~~~~~
permutation.cpp: In member function 'void Vec::build(std::vector<int>&)':
permutation.cpp:374:46: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
374 | if (blocks.back().vec.size() + 1 >= K) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
permutation.cpp: In member function 'void Vec::add(int, int)':
permutation.cpp:390:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Vec::Block>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
390 | for (int i = 0; i < blocks.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
permutation.cpp:391:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
391 | if (blocks[i].vec.size() >= ind) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~~~
permutation.cpp:398:42: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
398 | if (blocks[i].vec.size() > 2 * K) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~~~~
permutation.cpp: In member function 'void Vec::add_val(int, int)':
permutation.cpp:419:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Vec::Block>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
419 | for (int i = 0; i < blocks.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
permutation.cpp: In member function 'int Vec::find_el(int)':
permutation.cpp:447:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Vec::Block>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
447 | for (int i = 0; i < blocks.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
permutation.cpp:454:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
454 | for (int j = 0; j < blocks[i].vec.size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~~~~~
permutation.cpp:464:5: warning: control reaches end of non-void function [-Wreturn-type]
464 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1048 KB |
Output is correct |
| 3 |
Correct |
3 ms |
988 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1048 KB |
Output is correct |
| 3 |
Correct |
3 ms |
988 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
795 ms |
100180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1048 KB |
Output is correct |
| 3 |
Correct |
3 ms |
988 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
795 ms |
100180 KB |
Output is correct |
| 6 |
Correct |
1720 ms |
177716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1048 KB |
Output is correct |
| 3 |
Correct |
3 ms |
988 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
795 ms |
100180 KB |
Output is correct |
| 6 |
Correct |
1720 ms |
177716 KB |
Output is correct |
| 7 |
Runtime error |
988 ms |
135708 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1048 KB |
Output is correct |
| 3 |
Correct |
3 ms |
988 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
795 ms |
100180 KB |
Output is correct |
| 6 |
Correct |
1720 ms |
177716 KB |
Output is correct |
| 7 |
Runtime error |
988 ms |
135708 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1048 KB |
Output is correct |
| 3 |
Correct |
3 ms |
988 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
795 ms |
100180 KB |
Output is correct |
| 6 |
Correct |
1720 ms |
177716 KB |
Output is correct |
| 7 |
Runtime error |
988 ms |
135708 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
