// 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
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;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
276 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
276 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
304 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
3 ms |
304 KB |
Output is correct |
| 11 |
Correct |
3 ms |
212 KB |
Output is correct |
| 12 |
Correct |
3 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
3 ms |
212 KB |
Output is correct |
| 15 |
Correct |
2 ms |
212 KB |
Output is correct |
| 16 |
Correct |
3 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
276 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
304 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
3 ms |
304 KB |
Output is correct |
| 11 |
Correct |
3 ms |
212 KB |
Output is correct |
| 12 |
Correct |
3 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
3 ms |
212 KB |
Output is correct |
| 15 |
Correct |
2 ms |
212 KB |
Output is correct |
| 16 |
Correct |
3 ms |
212 KB |
Output is correct |
| 17 |
Incorrect |
4 ms |
212 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
