QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#609129 | #9412. Stop the Castle | orz_z | AC ✓ | 7ms | 33616kb | C++14 | 7.9kb | 2024-10-04 10:47:34 | 2024-10-04 10:47:35 |
Judging History
answer
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize("Ofast,fast-math")
//#pragma GCC target("avx,avx2")
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef double db;
#define F(i, a, b) for(int i = a; i <= (b); ++i)
#define F2(i, a, b) for(int i = a; i < (b); ++i)
#define dF(i, a, b) for(int i = a; i >= (b); --i)
template<typename T> void debug(string s, T x) {
cerr << "[" << s << "] = [" << x << "]\n";
}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {
for (int i = 0, b = 0; i < (int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++;
else if (s[i] == ')' || s[i] == '}') b--;
else if (s[i] == ',' && b == 0) {
cerr << "[" << s.substr(0, i) << "] = [" << x << "] | ";
debug(s.substr(s.find_first_not_of(' ', i + 1)), args...);
break;
}
}
#ifdef ONLINE_JUDGE
#define Debug(...)
#else
#define Debug(...) debug(#__VA_ARGS__, __VA_ARGS__)
#endif
#define pb push_back
#define fi first
#define se second
#define Mry fprintf(stderr, "%.3lf MB\n", (&Med - &Mbe) / 1048576.0)
#define Try cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
typedef long long ll;
// namespace Fread {const int SIZE = 1 << 17; char buf[SIZE], *S, *T; inline char getchar() {if (S == T) {T = (S = buf) + fread(buf, 1, SIZE, stdin); if (S == T) return '\n';} return *S++;}}
// namespace Fwrite {const int SIZE = 1 << 17; char buf[SIZE], *S = buf, *T = buf + SIZE; inline void flush() {fwrite(buf, 1, S - buf, stdout), S = buf;} inline void putchar(char c) {*S++ = c;if (S == T) flush();} struct NTR {~NTR() {flush();}} ztr;}
// #ifdef ONLINE_JUDGE
// #define getchar Fread::getchar
// #define putchar Fwrite::putchar
// #endif
inline int ri() {
int x = 0;
bool t = 0;
char c = getchar();
while (c < '0' || c > '9') t |= c == '-', c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
return t ? -x : x;
}
inline void wi(int x) {
if (x < 0) {
putchar('-'), x = -x;
}
if (x > 9) wi(x / 10);
putchar(x % 10 + 48);
}
inline void wi(int x, char s) {
wi(x), putchar(s);
}
bool Mbe;
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3f;
const int _ = 2e5 + 5;
int n, m;
template<class tp>
struct Flow {
int Node;
int s, t, lv[_], cur[_];
int tot = 1, head[_], to[_ << 1], nxt[_ << 1];
tp w[_ << 1];
inline void add(int u, int v, tp dis) {
to[++tot] = v;
nxt[tot] = head[u];
w[tot] = dis;
head[u] = tot;
}
inline void Add(int u, int v, tp dis) {
add(u, v, dis);
add(v, u, 0);
}
inline bool bfs() {
F(i, 0, Node) lv[i] = -1;
lv[s] = 0;
memcpy(cur, head, sizeof(head));
queue<int> q;
q.push(s);
while (!q.empty()) {
int p = q.front();
q.pop();
for (int eg = head[p]; eg; eg = nxt[eg]) {
int v = to[eg];
tp vol = w[eg];
if (vol > 0 && lv[v] == -1)
lv[v] = lv[p] + 1, q.push(v);
}
}
return lv[t] != -1;
}
tp dfs(int p, tp flow = 2e9) {
if (p == t)
return flow;
tp rmn = flow;
for (int eg = cur[p]; eg && rmn; eg = nxt[eg]) {
cur[p] = eg;
int v = to[eg];
tp vol = w[eg];
if (vol > 0 && lv[v] == lv[p] + 1) {
tp c = dfs(v, min(vol, rmn));
rmn -= c;
w[eg] -= c;
w[eg ^ 1] += c;
}
}
return flow - rmn;
}
inline tp dinic() {
tp ans = 0;
while (bfs())
ans += dfs(s);
return ans;
}
void init() {
F(i, 0, Node) head[i] = 0;
tot = 1;
Node = 0;
}
};
Flow<int> A;
pii a[_], b[_]; int t, C[_];
short mp[1605][1605], mp1[1605][1605], mp2[1605][1605];
bool Med;
signed main() {
// Mry;
int T = ri();
// int zkw = T;
while(T--) {
A.init();
n = ri();
t = 0;
F(i, 1, n) {
a[i].fi = ri(), a[i].se = ri();
C[++t] = a[i].fi, C[++t] = a[i].se;
C[++t] = a[i].fi - 1, C[++t] = a[i].fi + 1;
C[++t] = a[i].se - 1, C[++t] = a[i].se + 1;
}
m = ri();
F(i,1 , m) {
b[i].fi = ri(), b[i].se = ri();
C[++t] = b[i].fi, C[++t] = b[i].se;
}
// if(zkw == 20) {
//// F(i, 1, n) cout << a[i].fi << ' ' << a[i].se << ' ';
//// cout <<'\n';
// F(i, 1, m) cout << b[i].fi << ' ' << b[i].se << '\n';
// return 0;
// }
sort(C + 1, C + t + 1);
t = unique(C + 1, C + t + 1) - C - 1;
F(i, 1, n) {
a[i].fi = lower_bound(C + 1, C + t + 1, a[i].fi) - C;
a[i].se = lower_bound(C + 1, C + t + 1, a[i].se) - C;
Debug(i, a[i].fi, a[i].se);
}
F(i, 1, m) {
b[i].fi = lower_bound(C + 1, C + t + 1, b[i].fi) - C;
b[i].se = lower_bound(C + 1, C + t + 1, b[i].se) - C;
Debug(i, b[i].fi, b[i].se);
}
// t = 10;
F(i, 1, t) F(j, 1, t) {
mp[i][j] = mp1[i][j] = mp2[i][j] = 0;
}
F(i, 1, n) {
mp[a[i].fi][a[i].se] = 1;
}
F(i, 1, m) {
mp[b[i].fi][b[i].se] = 2;
}
// Debug("haha");
bool flg = 0;
int sum = 0;
int hangnode = 0, lienode = t + t + t;
static pii Zb[_];
F(i, 1, t) {
F(j, 1, t) if(mp[i][j] == 1) {
int nw = j + 1;
while(nw <= t && mp[i][nw] != 1) nw++;//, Debug(nw);
// Debug(i, j);
if(j < t && j + 1 == nw && mp[i][nw] == 1) {
flg = 1;
break;
}
// Debug(i, j, nw);
if(nw == t + 1) break;
bool fg = 1;
F(z, j + 1, nw - 1) {
fg &= (mp[i][z] == 0);
}
if(fg) {
++hangnode;
sum++;
// Debug("hang", i, j + 1, nw - 1);
F(z, j + 1, nw - 1) if(mp[i][z] == 0) mp1[i][z] = hangnode, Zb[hangnode] = {i, z};
}
// Debug(t, nw - 1, "done");
j = nw - 1;
}
// Debug(i);
if(flg) break;
}
if(flg) {
puts("-1");
continue;
}
// Debug("zj");
F(j, 1, t) {
F(i, 1, t) if(mp[i][j] == 1) {
int nw = i + 1;
while(nw <= t && mp[nw][j] != 1) nw++;
if(nw == t + 1) break;
if(i < t && i + 1 == nw && mp[nw][j] == 1) {
flg = 1;
break;
}
bool fg = 1;
F(z, i + 1, nw - 1) fg &= (mp[z][j] == 0);
if(fg) {
++lienode;
sum++;
// Debug("lie", i + 1, nw - 1, j);
F(z, i + 1, nw - 1) if(mp[z][j] == 0) mp2[z][j] = lienode, Zb[lienode] = {z, j};
}
i = nw - 1;
}
if(flg) break;
}
if(flg) {
puts("-1");
continue;
}
// Debug("114514");
A.s = 0, A.t = lienode + 1;
A.Node = A.t + 2;
F(i, 1, hangnode) A.Add(A.s, i, 1);
F(i, t + t + t + 1, lienode) A.Add(i, A.t, 1);
// Debug(hangnode, t + t + t, lienode);
vector<tuple<int, int, int, int, int>> g;
F(i, 1, t) F(j, 1, t) if(mp1[i][j] && mp2[i][j]) {
// Debug(i, j);
g.pb({A.tot + 1, i, j, mp1[i][j], mp2[i][j]});
A.Add(mp1[i][j], mp2[i][j], 1);
}
static int Flg[_];
F(i, 1, lienode) Flg[i] = 0;
int w = A.dinic();
// Debug(sum, w);
cout<<sum - w << '\n';
for(auto v : g) {
int a, b, c, d, e;
tie(a, b, c, d, e) = v;
if(A.w[a] == 0) {
cout << C[b] << ' ' << C[c] << '\n';
Flg[d] = Flg[e] = 1;
}
}
F(i, 1, hangnode) if(!Flg[i]) {
cout << C[Zb[i].fi] << ' ' <<C[Zb[i].se] << '\n';
}
F(i, t + t + t + 1, lienode) if(!Flg[i]) {
cout << C[Zb[i].fi] << ' ' <<C[Zb[i].se] << '\n';
}
}
// Try;
return 0;
}
/*
1
13
89287395 441913071
89287395 590314987
142917372 582720391
142917372 598813561
232930851 582720391
263974835 468188689
263974835 490702144
543529670 152471388
543529670 219371706
647691663 598813561
772865038 598813561
773363571 482933265
773363571 561453301
8
128947560 120560639
264980960 474213553
266089174 284660056
266089174 468188689
266089174 479939365
522529834 299821858
543529670 468188689
550434845 878736621
1
7
1 3
6 6
4 7
2 1
6 3
4 1
2 6
3
3 4
6 4
3 1
4
7
1 3
6 6
4 7
2 1
6 3
4 1
2 6
3
3 4
6 4
3 1
2
1 1
2 2
0
3
1 1
1 3
3 3
1
1 2
3
1 1
1 3
2 3
0
*/
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 28240kb
input:
4 7 1 3 6 6 4 7 2 1 6 3 4 1 2 6 3 3 4 6 4 3 1 2 1 1 2 2 0 3 1 1 1 3 3 3 1 1 2 3 1 1 1 3 2 3 0
output:
2 2 3 4 6 0 1 2 3 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: 0
Accepted
time: 3ms
memory: 26216kb
input:
21 11 3 5 18 6 19 12 27 48 28 38 30 12 33 18 42 18 43 38 45 46 48 34 3 2 6 24 4 41 45 15 11 6 15 27 16 9 16 14 16 48 19 26 25 12 27 26 28 4 31 40 32 6 33 50 37 50 46 11 50 29 17 1 49 4 9 9 15 9 22 11 31 11 46 14 28 17 5 17 49 18 43 20 31 30 46 33 11 33 33 34 15 36 6 47 10 2 16 46 36 30 11 7 34 7 41 ...
output:
3 29 12 41 18 42 38 5 16 13 16 47 31 6 26 26 36 50 0 1 42 10 0 1 43 35 5 1 11 1 40 33 47 44 46 43 44 0 5 27 41 29 40 44 38 10 1 31 15 1 32 12 0 0 0 0 6 23 10 35 34 12 40 23 45 29 33 34 46 0 3 20 31 43 32 34 17 0 -1 3 16 36 25 12 31 39 6 7 5 8 11 5 5 6 6 9 9 10 10
result:
ok ok 21 cases (21 test cases)
Test #3:
score: 0
Accepted
time: 7ms
memory: 31972kb
input:
2 200 7 52 9 160 10 4 12 61 18 436 19 430 20 499 24 139 25 416 29 53 33 153 35 275 35 310 37 25 38 477 39 349 42 120 44 158 45 330 49 486 50 204 51 67 52 138 52 305 56 139 63 132 66 4 67 327 70 484 71 67 72 308 74 218 76 479 81 139 82 90 86 201 87 335 91 35 91 220 92 496 94 29 94 436 96 359 97 299 1...
output:
46 52 139 91 160 94 35 126 61 132 67 154 138 154 496 185 147 187 467 199 432 224 153 260 275 270 305 277 356 306 374 311 186 334 367 349 61 352 112 393 307 35 309 126 300 187 451 224 431 261 492 274 111 277 271 311 481 390 366 440 191 453 375 65 4 143 25 351 35 70 67 80 139 333 177 278 186 289 272 4...
result:
ok ok 2 cases (2 test cases)
Test #4:
score: 0
Accepted
time: 3ms
memory: 26668kb
input:
20 13 89287395 441913071 89287395 590314987 142917372 582720391 142917372 598813561 232930851 582720391 263974835 468188689 263974835 490702144 543529670 152471388 543529670 219371706 647691663 598813561 772865038 598813561 773363571 482933265 773363571 561453301 8 128947560 120560639 264980960 4742...
output:
8 89287395 590314986 142917372 598813560 263974835 490702143 543529670 219371705 773363571 561453300 232930850 582720391 647691662 598813561 772865037 598813561 7 808969359 818037531 808969359 762966372 808969359 917024052 869847376 354711322 183418802 358274214 808969358 762966373 203395425 8719512...
result:
ok ok 20 cases (20 test cases)
Test #5:
score: 0
Accepted
time: 0ms
memory: 30504kb
input:
2 184 35763790 435860426 152681166 443483111 261932524 745277126 261932524 787982418 314305867 342102981 314305867 522593781 314305867 747023891 314305867 811404535 314305867 816914009 314305867 857896659 319901983 797458033 321347896 342102981 332550928 902179526 343207116 914408792 350635050 15515...
output:
160 314305867 787982418 350635050 435860426 350635050 811404535 407380694 797458033 469496529 342102981 469496529 438907614 469496529 732085440 469496529 816914009 469496529 837963933 495537855 461654555 496813081 699021890 496813081 787982418 496813081 815487777 496813081 857896659 520115644 751818...
result:
ok ok 2 cases (2 test cases)
Test #6:
score: 0
Accepted
time: 4ms
memory: 30076kb
input:
2 193 78368109 329329995 87932514 657474465 87932514 903492853 94608574 845872655 103602204 88649154 124431127 405860533 145262472 108198774 145262472 907127202 154400439 136367504 165270984 773451933 184157521 409828915 197728547 291882089 197728547 609623645 211750768 843867422 246178069 108396139...
output:
145 145262472 903492853 197728547 409828915 246178069 291882089 291242118 564718673 365329221 136367504 365329221 211655411 365329221 405860533 365329221 657489855 365329221 773451933 365329221 845872655 382558552 984789430 385064292 502303728 391226954 843867422 410833945 564718673 412106895 135814...
result:
ok ok 2 cases (2 test cases)
Test #7:
score: 0
Accepted
time: 3ms
memory: 32360kb
input:
2 192 1075648 579875717 1075648 937648715 1393060 191616432 3957616 541362608 3957616 971879257 5415801 541362608 5887448 541362608 5887448 624842533 25767120 610618164 26193206 214214028 26193206 231445627 26727662 374314271 29550509 755417826 29550509 917592925 30033126 610618164 31134588 58188305...
output:
131 31134588 231445627 33207011 541362608 46425938 755417826 250896470 264208611 295641139 541362608 333807226 762642201 340743563 288390629 341366249 231445627 360971009 755417826 417168695 231445627 417966308 381919591 418600362 755417826 429088204 541362608 509798823 541362608 509798823 741119775...
result:
ok ok 2 cases (2 test cases)
Test #8:
score: 0
Accepted
time: 3ms
memory: 26280kb
input:
20 14 378192988 147499872 378192988 837331700 449924898 147499872 449924898 837331700 592684636 147499872 592684636 837331700 783332532 147499872 783332532 837331700 378192988 197547597 783332532 197547597 378192988 343857831 783332532 343857831 378192988 576579017 783332532 576579017 2 449924898 19...
output:
15 378192988 197547596 378192988 343857830 378192988 576579016 378192988 837331699 783332532 197547596 783332532 343857830 783332532 576579016 783332532 837331699 449924897 147499872 592684635 147499872 783332531 147499872 783332531 576579017 449924897 837331700 592684635 837331700 783332531 8373317...
result:
ok ok 20 cases (20 test cases)
Test #9:
score: 0
Accepted
time: 0ms
memory: 29512kb
input:
2 200 8623893 3649468 8623893 989134714 24820918 3649468 24820918 989134714 43705451 3649468 43705451 989134714 45500146 3649468 45500146 989134714 58265855 3649468 58265855 989134714 112263159 3649468 112263159 989134714 126496650 3649468 126496650 989134714 137574156 3649468 137574156 989134714 14...
output:
249 24820918 6255307 43705451 11610914 45500146 23366504 58265855 28938721 112263159 31914492 126496650 36029445 137574156 66226935 140089445 84152868 156036789 132710904 170794245 149083019 176576709 174305881 186774359 180413073 194114590 195080121 222368048 231772824 237249112 234663336 250839457...
result:
ok ok 2 cases (2 test cases)
Test #10:
score: 0
Accepted
time: 0ms
memory: 31032kb
input:
2 200 2691939 27674656 2691939 984614319 30225807 27674656 30225807 984614319 39388076 27674656 39388076 984614319 55883389 27674656 55883389 984614319 77258752 27674656 77258752 984614319 106874917 27674656 106874917 984614319 144383292 27674656 144383292 984614319 145360776 27674656 145360776 9846...
output:
216 279200011 293316179 347252805 363531956 446662965 376231503 496057717 383623456 514655989 390555088 523731402 441004197 538628510 490065400 562810007 540189713 630132600 545422987 631858791 565468975 643299496 646360861 754008138 861149655 782710197 901945895 2691939 69029839 2691939 160188717 2...
result:
ok ok 2 cases (2 test cases)
Test #11:
score: 0
Accepted
time: 0ms
memory: 33616kb
input:
2 200 1005937 7 3412691 7 5764908 7 7897785 7 8061992 7 12801501 7 18529696 7 22574605 7 25203351 7 34574958 7 34998216 7 40928451 7 49792193 7 55962320 7 59632864 7 62353373 7 62611196 7 65346591 7 71459320 7 71550121 7 72215989 7 82584263 7 86119549 7 96204862 7 96940713 7 97693112 7 102067050 7 1...
output:
199 3412690 7 5764907 7 7897784 7 8061991 7 12801500 7 18529695 7 22574604 7 25203350 7 34574957 7 34998215 7 40928450 7 49792192 7 55962319 7 59632863 7 62353372 7 62611195 7 65346590 7 71459319 7 71550120 7 72215988 7 82584262 7 86119548 7 96204861 7 96940712 7 97693111 7 102067049 7 105454642 7 1...
result:
ok ok 2 cases (2 test cases)
Extra Test:
score: 0
Extra Test Passed