Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#define _GLIBCXX_DEBUG
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> pii;
- typedef vector<int> vi;
- #define mk make_pair
- #define inb push_back
- #define X first
- #define Y second
- #define all(v) v.begin(), v.end()
- #define sqr(x) (x) * (x)
- /** 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;
- }
- template <class T>
- inline T readInt() {
- int s = 1, c = readChar();
- T x = 0;
- if (c == '-')
- s = -1, c = getChar();
- else if (c == '+')
- c = getChar();
- while ('0' <= c && c <= '9')
- x = x * 10 + c - '0', 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(9, (int)x);
- writeChar('0' + t), x -= t;
- }
- x *= 10;
- t = std::min(9, (int)(x + 0.5));
- writeChar('0' + t);
- }
- int solve();
- int main()
- {
- //ios_base::sync_with_stdio(0);
- //cin.tie(0);
- #define TASK "carno"
- #ifndef _DEBUG
- //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
- #endif
- solve();
- }
- const int K = 322;
- struct SqrtDecomposition
- {
- vector<vector<int>> bl;
- set<int> ok;
- SqrtDecomposition(int n)
- {
- for (int i = 0, idb = 0; i < n; i += K, ++idb)
- {
- bl.inb({});
- for (int j = 0; i + j < min(i + K, n); ++j)
- {
- ok.insert(i + j);
- bl[idb].inb(0);
- }
- }
- };
- pii get_block(int x)
- {
- int idb = 0;
- for (auto &v : bl)
- {
- if (x >= (int)v.size())
- {
- x -= (int)v.size();
- }
- else
- {
- break;
- }
- ++idb;
- }
- return mk(idb, x);
- }
- void trykill(int idl)
- {
- if (!bl[idl].empty() || bl.size() == 1)
- return;
- bl.erase(bl.begin() + idl);
- }
- void balance(int idl)
- {
- if (bl[idl].size() < 2 * K)
- return;
- vi nbl;
- int sz = bl[idl].size();
- while ((int)bl[idl].size() >= sz / 2)
- {
- nbl.inb(bl[idl].back());
- bl[idl].pop_back();
- }
- reverse(all(nbl));
- bl.insert(bl.begin() + idl + 1, nbl);
- }
- void insert(int pos, int x)
- {
- pii res = get_block(pos);
- int l = res.X;
- int id = max(res.Y, 0);
- int nxt0 = *ok.lower_bound(pos);
- if (bl[l][id])
- {
- del(nxt0);
- bl[l].insert(bl[l].begin() + id, x);
- }
- else
- {
- bl[l][id] = x;
- }
- ok.erase(nxt0);
- balance(l);
- }
- void del(int pos)
- {
- pii res = get_block(pos);
- int l = res.X;
- int id = res.Y;
- bl[l].erase(bl[l].begin() + id);
- trykill(l);
- }
- void collect(vector<int>& ans)
- {
- ans.clear();
- for (auto &v : bl)
- {
- for (auto &x : v)
- {
- ans.inb(x);
- }
- }
- while (!ans.back())
- ans.pop_back();
- }
- };
- int solve()
- {
- int n = readInt(), m = readInt();
- SqrtDecomposition T = SqrtDecomposition(n + m);
- auto printans = [&]()
- {
- vi ans;
- T.collect(ans);
- printf("%d\n", (int)ans.size());
- for (int x : ans)
- printf("%d ", x);
- puts("");
- };
- for (int i = 1; i <= n; ++i)
- {
- T.insert(readInt() - 1, i);
- }
- printans();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement