Submission #643866

#	Time	Username	Problem	Language	Result	Execution time	Memory
643866		alexchist	Permutation Recovery (info1cup17_permutation)	C++17	71 / 100	1720 ms	177716 KiB

Main

#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 (stderr)

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 |     }
      |     ^

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