Submission #580577

#	Time	Username	Problem	Language	Result	Execution time	Memory
580577		maomao90	On the Grid (FXCUP4_grid)	C++17	43 / 100	4 ms	304 KiB

grid

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
#include "grid.h"
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 1005;

int n;
bool done[MAXN];
int mpa[MAXN];

template <class T>
vector<T> shift(vector<T> p, int x) {
    vector<T> res = p;
    REP (i, 0, SZ(p)) {
        if (i - x < 0) {
            res[i] = p[i - x + SZ(p)];
        } else {
            res[i] = p[i - x];
        }
    }
    return res;
}

vi SortDisks(int N) {
    n = N;
    vi ans(n, -1);
    vi p(n, 0);
    iota(ALL(p), 0);
    int init = PutDisks(p);
    vii stk;
    stk.pb({0, init});
    while (1) {
        auto [i, v] = stk.back();
        int nv = -1;
        int lo = i + 1, hi = n;
        while (lo < hi) {
            int mid = lo + hi >> 1;
            int cv = PutDisks(shift(p, mid));
            if (cv + mid != v + i) {
                nv = cv;
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        if (hi == n) {
            assert(nv == -1);
            break;
        }
        assert(nv != -1);
        stk.pb({hi, nv});
    }
    REP (i, 0, SZ(stk)) {
        if (stk[i].SE == 2 * n - 1) {
            stk = shift(stk, SZ(stk) - i);
            break;
        }
    }
    p = shift(p, stk[0].FI);
    REP (i, 1, SZ(stk)) {
        stk[i].FI -= stk[0].FI;
        if (stk[i].FI < 0) {
            stk[i].FI += n;
        }
    }
    stk[0].FI = 0;
    vii tstk;
    tstk.pb(stk[0]);
    REP (i, 1, SZ(stk)) {
        auto [j, jv] = tstk.back();
        auto [k, kv] = stk[i];
        if (jv + j != kv + k) {
            tstk.pb(stk[i]);
        }
    }
    stk = tstk;
    REP (i, 0, SZ(stk)) {
        cerr << stk[i].FI << ' ' << stk[i].SE << '\n';
    }
    for (auto [i, x] : stk) {
        int v = x - (n - 1);
        ans[p[(n - i) % n]] = v;
        mpa[v] = p[(n - i) % n];
        done[v] = 1;
        cerr << p[(n - i) % n] << ": " << v << '\n';
    }
    vi np;
    REP (i, 1, n + 1) {
        if (done[i]) {
            np.pb(mpa[i]);
        }
    }
    REP (i, 0, n) {
        if (ans[p[i]] == -1) {
            np.pb(p[i]);
        }
    }
    assert(SZ(np) == n);
    p = np;
    REP (i, 0, n) {
        cerr << p[i] << ' ';
    }
    cerr << '\n';
    int zz = 2;
    while (1) {
        int nv = -1;
        int ds = 0;
        REP (i, 0, n) {
            if (ans[i] != -1) {
                ds++;
            }
        }
        int lo = 1, hi = n - ds + 1;
        while (lo < hi) {
            int mid = lo + hi >> 1;
            int cv = PutDisks(shift(p, mid));
            if (cv + mid != n + n - ds) {
                nv = cv;
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        cerr << hi << ' ' << nv << '\n';
        if (hi == n - ds + 1) {
            assert(nv == -1);
            int v = n - ds;
            RREP (i, n - 1, ds) {
                ans[p[i]] = v;
                mpa[v] = p[i];
                done[v] = 1;
                v--;
            }
            break;
        }
        assert(nv != -1);
        int v = nv - (n - 1);
        ans[p[(n - hi) % n]] = v;
        mpa[v] = p[(n - hi) % n];
        done[v] = 1;
        cerr << p[(n - hi) % n] << ": " << v << '\n';
        vi np;
        REP (i, 1, n + 1) {
            if (done[i]) {
                np.pb(mpa[i]);
            }
        }
        REP (i, 0, n) {
            if (ans[p[i]] == -1) {
                np.pb(p[i]);
            }
        }
        assert(SZ(np) == n);
        p = np;
        REP (i, 0, n) {
            cerr << p[i] << ' ';
        }
        cerr << '\n';
    }
    return ans;
}

Compilation message (stderr)

grid.cpp: In function 'vi SortDisks(int)':
grid.cpp:69:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |             int mid = lo + hi >> 1;
      |                       ~~~^~~~
grid.cpp:147:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  147 |             int mid = lo + hi >> 1;
      |                       ~~~^~~~
grid.cpp:136:9: warning: unused variable 'zz' [-Wunused-variable]
  136 |     int zz = 2;
      |         ^~

• Subtask 1: 12 / 12
• Subtask 2: 31 / 31
• Subtask 3: 0 / 57