QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#628654 | #7721. Flow Problem | PlentyOfPenalty# | RE | 0ms | 0kb | C++20 | 3.3kb | 2024-10-10 21:27:43 | 2024-10-10 21:27:44 |
answer
#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl '\n'
#define log(...) (void(0))
#endif
using namespace std;
using ll = long long;
using lf = long double;
using ull = unsigned long long;
const int N = 4005;
const int Lim_N = 1000;
const int Lim_T = 2002;
// const int Lim_N = 15;
// const int Lim_T = 32;
struct sta {
int x, n;
} pb[N];
struct pos {
int x, y;
} nw, res[N];
int sz;
pos Next(pos p, sta s, int t) {
if (p.x == s.x) {
p.y = (p.y + t) % (s.n << 1);
if (p.y >= s.n) p.x ^= 1, p.y = (s.n << 1) - 1 - p.y;
} else {
p.y = (s.n << 1) - 1 - p.y;
p.y = (p.y + t) % (s.n << 1);
if (p.y >= s.n) p.y = (s.n << 1) - 1 - p.y;
else
p.x ^= 1;
}
return p;
}
#define Ind(P) (P.x * Lim_N + P.y);
int vis[N], TIM, cnt[N], fl[N];
int mns;
string tmp;
int Get_best(pos p, int flg) {
// log("GETBEST %d %d %d\n", p.x, p.y, flg);
mns = sz;
int mni = 1, mx, ind, tg;
for (int i = 1; i <= Lim_T; ++i) {
// log("---------------i=%d\n", i);
++TIM;
mx = 0;
tg = 1;
// log("sz=%d\n", sz);
for (int j = 1; j <= sz; ++j) {
res[j] = Next(p, pb[j], i);
ind = Ind(res[j]);
// log("INDof (%d,%d)=%d %d\n", pb[j].n, pb[j].x, res[j].x, res[j].y);
if (vis[ind] != TIM) {
vis[ind] = TIM;
cnt[ind] = 0;
fl[ind] = pb[j].x;
}
++cnt[ind];
if (fl[ind] != pb[j].x) tg = 0;
mx = max(mx, cnt[ind]);
}
// log("STEP=%d,mx=%d,tg=%d\n", i, mx, tg);
if (flg && !tg) continue;
if (mx <= mns) {
mns = mx;
mni = i;
}
}
return mni;
}
void Do(int t) {
cout << "wait " << t << "\n" << flush;
pos to;
cin >> tmp;
cin >> to.x >> to.y;
int tsz = 0;
for (int i = 1; i <= sz; ++i) {
if (pb[i].n <= to.y) continue;
res[i] = Next(nw, pb[i], t);
// log("RES %d=%d %d\n", i, res[i].x, res[i].y);
if (res[i].x == to.x && res[i].y == to.y) {
// log("FIND %d %d\n", pb[i].x, pb[i].n);
pb[++tsz] = pb[i];
}
}
sz = tsz;
nw = to;
assert(sz);
}
void Switch() {
cout << "switch\n" << flush;
pos to;
cin >> tmp;
cin >> to.x >> to.y;
nw = to;
}
void End(string s) {
cout << s << "\n" << flush;
cin >> tmp;
}
int dir, n;
int main() {
#ifdef memset0
// freopen("F.in", "r", stdin);
#endif
// cin.tie(0)->sync_with_stdio(0);
cin >> nw.x >> nw.y;
for (int i = max(2, nw.y + 1); i <= Lim_N; ++i) {
pb[++sz] = (sta){0, i};
pb[++sz] = (sta){1, i};
}
Do(Get_best(nw, 1));
Do(Get_best(nw, 0));
dir = pb[1].x;
for (int i = 1; i <= sz; ++i) assert(pb[i].x == dir);
if (dir == nw.x) Switch();
Do(nw.y);
End("Left");
// assert(tmp[0] == 'y');
cin >> nw.x >> nw.y;
int tsz = 0;
for (int i = 1; i <= sz; ++i) {
if (pb[i].n <= nw.y) continue;
pb[++tsz] = pb[i];
}
sz = tsz;
int tpos = Get_best((pos){nw.x ^ 1, nw.y}, 0);
int tmn = mns;
int npos = Get_best(nw, 0);
if (tmn < mns) {
mns = tmn;
npos = tpos;
Switch();
}
Do(npos);
// assert(sz == 1);
n = pb[1].n;
if (dir == nw.x) Do(n - 1 - nw.y);
else
Do(nw.y + n);
End("Right");
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
0 5 no 0 0 no 1 4 no 0 4 no 0 0
output:
wait 5 wait 1485 switch wait 4 Left