QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#628698 | #7721. Flow Problem | PlentyOfPenalty# | RE | 23ms | 3848kb | C++20 | 3.6kb | 2024-10-10 21:46:00 | 2024-10-10 21:47:41 |
Judging History
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;
int TEST;
struct sta {
int x, n;
} pb[N], tar;
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;
if (!TEST) {
cin >> tmp;
cin >> to.x >> to.y;
} else {
to = Next(nw, tar, t);
log("TO %d %d\n", 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;
if (!TEST) {
cin >> tmp;
cin >> to.x >> to.y;
} else {
to = nw;
to.x ^= 1;
log("TO %d %d\n", to.x, to.y);
}
nw = to;
}
void End(string s) {
cout << s << "\n" << flush;
if (!TEST) {
cin >> tmp;
} else {
tmp = "yes";
}
}
int dir, n;
int main() {
#ifdef memset0
// freopen("F.in", "r", stdin);
cin >> tar.x >> tar.n;
TEST = 1;
#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();
}
log("REM=%d\n", mns);
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: 100
Accepted
time: 21ms
memory: 3664kb
input:
0 5 no 0 0 no 1 4 no 0 4 no 0 0 yes 1 2 no 0 10 no 1 19 yes
output:
wait 5 wait 1485 switch wait 4 left wait 1987 wait 30 right
result:
ok OK
Test #2:
score: 0
Accepted
time: 20ms
memory: 3616kb
input:
1 0 no 1 1 no 0 0 no 0 0 yes 1 0 no 0 1 no 1 1 yes
output:
wait 1 wait 1482 wait 0 left wait 2002 wait 3 right
result:
ok OK
Test #3:
score: 0
Accepted
time: 20ms
memory: 3552kb
input:
0 0 no 1 0 no 0 0 no 0 0 yes 0 0 no 1 1 no 1 1 yes
output:
wait 1 wait 1483 wait 0 left wait 2002 wait 0 right
result:
ok OK
Test #4:
score: 0
Accepted
time: 22ms
memory: 3664kb
input:
1 2 no 1 0 no 0 1 no 1 1 no 1 0 yes 0 0 no 1 1 no 0 2 yes
output:
wait 2 wait 1484 switch wait 1 left wait 2002 wait 4 right
result:
ok OK
Test #5:
score: 0
Accepted
time: 20ms
memory: 3848kb
input:
1 0 no 0 0 no 0 1 no 1 1 no 1 0 yes 1 2 no 0 1 no 0 2 yes
output:
wait 1 wait 1483 switch wait 1 left wait 2002 wait 1 right
result:
ok OK
Test #6:
score: 0
Accepted
time: 21ms
memory: 3704kb
input:
1 2 no 1 0 no 0 3 no 1 3 no 1 0 yes 0 2 no 1 2 no 0 3 yes
output:
wait 2 wait 1484 switch wait 3 left wait 1987 wait 6 right
result:
ok OK
Test #7:
score: 0
Accepted
time: 15ms
memory: 3704kb
input:
1 3 no 0 1 no 1 0 no 0 0 no 0 0 yes 1 3 no 0 2 no 1 3 yes
output:
wait 3 wait 2002 switch wait 0 left wait 2002 wait 6 right
result:
ok OK
Test #8:
score: 0
Accepted
time: 23ms
memory: 3592kb
input:
0 0 no 0 1 no 0 3 no 1 3 no 1 0 yes 1 2 no 1 0 no 0 4 yes
output:
wait 1 wait 1482 switch wait 3 left wait 1992 wait 5 right
result:
ok OK
Test #9:
score: 0
Accepted
time: 20ms
memory: 3640kb
input:
1 0 no 1 1 no 1 3 no 0 3 no 0 0 yes 1 4 no 0 0 no 1 4 yes
output:
wait 1 wait 1482 switch wait 3 left wait 1985 wait 5 right
result:
ok OK
Test #10:
score: 0
Accepted
time: 15ms
memory: 3828kb
input:
1 3 no 0 5 no 1 4 no 0 4 no 0 0 yes 0 1 no 0 3 no 1 5 yes
output:
wait 3 wait 2002 switch wait 4 left wait 2002 wait 9 right
result:
ok OK
Test #11:
score: -100
Runtime Error
input:
1 3 no 1 0 no 1 4 no 1 0 yes 0 2 no 1 2
output:
wait 3 wait 1484 wait 4 left wait 1795