0000: 23 69 6e 63 6c 75 64 65 20 3c 69 6f 73 74 72 65 #include <iostre
0010: 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 am>..#include <s
0020: 73 74 72 65 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 stream>..#includ
0030: 65 20 3c 69 6f 6d 61 6e 69 70 3e 0d 0a 23 69 6e e <iomanip>..#in
0040: 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 3e 0d 0a clude <vector>..
0050: 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 6e 67 #include <string
0060: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 6d 61 70 >..#include <map
0070: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 65 74 >..#include <set
0080: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 61 6c 67 >..#include <alg
0090: 6f 72 69 74 68 6d 3e 0d 0a 23 69 6e 63 6c 75 64 orithm>..#includ
00a0: 65 20 3c 6e 75 6d 65 72 69 63 3e 0d 0a 23 69 6e e <numeric>..#in
00b0: 63 6c 75 64 65 20 3c 69 74 65 72 61 74 6f 72 3e clude <iterator>
00c0: 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 66 75 6e 63 ..#include <func
00d0: 74 69 6f 6e 61 6c 3e 0d 0a 23 69 6e 63 6c 75 64 tional>..#includ
00e0: 65 20 3c 63 6f 6d 70 6c 65 78 3e 0d 0a 23 69 6e e <complex>..#in
00f0: 63 6c 75 64 65 20 3c 71 75 65 75 65 3e 0d 0a 23 clude <queue>..#
0100: 69 6e 63 6c 75 64 65 20 3c 73 74 61 63 6b 3e 0d include <stack>.
0110: 0a 23 69 6e 63 6c 75 64 65 20 3c 63 6d 61 74 68 .#include <cmath
0120: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 61 73 >..#include <cas
0130: 73 65 72 74 3e 0d 0a 75 73 69 6e 67 20 6e 61 6d sert>..using nam
0140: 65 73 70 61 63 65 20 73 74 64 3b 0d 0a 74 79 70 espace std;..typ
0150: 65 64 65 66 20 6c 6f 6e 67 20 6c 6f 6e 67 20 4c edef long long L
0160: 4c 3b 0d 0a 74 79 70 65 64 65 66 20 6c 6f 6e 67 L;..typedef long
0170: 20 64 6f 75 62 6c 65 20 4c 44 3b 0d 0a 74 79 70 double LD;..typ
0180: 65 64 65 66 20 63 6f 6d 70 6c 65 78 3c 4c 44 3e edef complex<LD>
0190: 20 43 4d 50 3b 0d 0a 0d 0a 0d 0a 2f 2f 2d 2d 2d CMP;......//---
01a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
01b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
01c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
01d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0d 0a 2f 2f 20 44 ----------..// D
01e0: 69 6e 69 63 27 73 20 41 6c 67 6f 72 69 74 68 6d inic's Algorithm
01f0: 0d 0a 2f 2f 20 20 20 4f 28 56 20 45 29 0d 0a 2f ..// O(V E)../
0200: 2f 0d 0a 2f 2f 20 47 20 3a 20 62 69 64 69 72 65 /..// G : bidire
0210: 63 74 69 6f 6e 61 6c 20 28 47 5b 69 5d 2e 68 61 ctional (G[i].ha
0220: 73 28 6a 29 20 3c 3d 3d 3e 20 47 5b 6a 5d 2e 68 s(j) <==> G[j].h
0230: 61 73 28 69 29 29 0d 0a 2f 2f 20 46 20 3a 20 66 as(i))..// F : f
0240: 6c 6f 77 2d 63 61 70 61 63 69 74 79 20 46 5b 69 low-capacity F[i
0250: 5d 5b 6a 5d 20 3d 20 43 61 70 61 63 69 74 79 2c ][j] = Capacity,
0260: 20 46 5b 6a 5d 5b 69 5d 20 3d 20 30 0d 0a 2f 2f F[j][i] = 0..//
0270: 0d 0a 2f 2f 20 56 65 72 69 66 69 65 64 20 62 79 ..// Verified by
0280: 0d 0a 2f 2f 20 20 20 2d 20 53 52 4d 20 33 39 39 ..// - SRM 399
0290: 20 44 69 76 31 20 4c 56 33 0d 0a 2f 2f 20 20 20 Div1 LV3..//
02a0: 2d 20 50 4b 55 20 31 34 35 39 0d 0a 2f 2f 20 20 - PKU 1459..//
02b0: 20 2d 20 43 6f 64 65 43 72 61 66 74 20 30 39 20 - CodeCraft 09
02c0: 43 55 54 53 0d 0a 2f 2f 20 20 20 2d 20 53 52 4d CUTS..// - SRM
02d0: 20 34 36 35 20 44 69 76 31 20 4c 56 32 0d 0a 2f 465 Div1 LV2../
02e0: 2f 20 20 20 2d 20 53 52 4d 20 35 34 33 20 44 69 / - SRM 543 Di
02f0: 76 31 20 4c 56 33 0d 0a 2f 2f 2d 2d 2d 2d 2d 2d v1 LV3..//------
0300: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0310: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0320: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0330: 2d 2d 2d 2d 2d 2d 2d 0d 0a 0d 0a 74 65 6d 70 6c -------....templ
0340: 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e 0d ate<typename T>.
0350: 0a 63 6c 61 73 73 20 49 64 47 65 6e 0d 0a 7b 0d .class IdGen..{.
0360: 0a 09 6d 61 70 3c 54 2c 20 69 6e 74 3e 20 76 32 ..map<T, int> v2
0370: 69 64 5f 3b 0d 0a 09 76 65 63 74 6f 72 3c 54 3e id_;...vector<T>
0380: 20 20 20 69 64 32 76 5f 3b 0d 0a 70 75 62 6c 69 id2v_;..publi
0390: 63 3a 0d 0a 09 69 6e 74 20 76 32 69 64 28 63 6f c:...int v2id(co
03a0: 6e 73 74 20 54 26 20 76 29 20 7b 0d 0a 09 09 69 nst T& v) {....i
03b0: 66 28 20 21 76 32 69 64 5f 2e 63 6f 75 6e 74 28 f( !v2id_.count(
03c0: 76 29 20 29 20 7b 20 76 32 69 64 5f 5b 76 5d 20 v) ) { v2id_[v]
03d0: 3d 20 73 69 7a 65 28 29 3b 20 69 64 32 76 5f 2e = size(); id2v_.
03e0: 70 75 73 68 5f 62 61 63 6b 28 76 29 3b 20 7d 0d push_back(v); }.
03f0: 0a 09 09 72 65 74 75 72 6e 20 76 32 69 64 5f 5b ...return v2id_[
0400: 76 5d 3b 0d 0a 09 7d 0d 0a 09 63 6f 6e 73 74 20 v];...}...const
0410: 54 26 20 69 64 32 76 28 69 6e 74 20 69 29 20 63 T& id2v(int i) c
0420: 6f 6e 73 74 20 7b 20 72 65 74 75 72 6e 20 69 64 onst { return id
0430: 32 76 5f 5b 69 5d 3b 20 7d 0d 0a 09 69 6e 74 20 2v_[i]; }...int
0440: 73 69 7a 65 28 29 20 63 6f 6e 73 74 20 7b 20 72 size() const { r
0450: 65 74 75 72 6e 20 69 64 32 76 5f 2e 73 69 7a 65 eturn id2v_.size
0460: 28 29 3b 20 7d 0d 0a 7d 3b 0d 0a 0d 0a 74 65 6d (); }..};....tem
0470: 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 56 plate<typename V
0480: 65 72 74 2c 20 74 79 70 65 6e 61 6d 65 20 46 6c ert, typename Fl
0490: 6f 77 2c 20 69 6e 74 20 4e 56 3d 32 30 34 38 3e ow, int NV=2048>
04a0: 0d 0a 63 6c 61 73 73 20 4d 61 78 46 6c 6f 77 0d ..class MaxFlow.
04b0: 0a 7b 0d 0a 09 49 64 47 65 6e 3c 56 65 72 74 3e .{...IdGen<Vert>
04c0: 20 69 64 67 65 6e 3b 0d 0a 09 76 65 63 74 6f 72 idgen;...vector
04d0: 3c 69 6e 74 3e 20 47 5b 4e 56 5d 3b 0d 0a 09 46 <int> G[NV];...F
04e0: 6c 6f 77 20 46 5b 4e 56 5d 5b 4e 56 5d 3b 0d 0a low F[NV][NV];..
04f0: 0d 0a 70 75 62 6c 69 63 3a 0d 0a 09 76 6f 69 64 ..public:...void
0500: 20 61 64 64 45 64 67 65 28 20 56 65 72 74 20 73 addEdge( Vert s
0510: 5f 2c 20 56 65 72 74 20 74 5f 2c 20 46 6c 6f 77 _, Vert t_, Flow
0520: 20 66 20 29 0d 0a 09 7b 0d 0a 09 09 63 6f 6e 73 f )...{....cons
0530: 74 20 69 6e 74 20 73 20 3d 20 69 64 67 65 6e 2e t int s = idgen.
0540: 76 32 69 64 28 73 5f 29 2c 20 74 20 3d 20 69 64 v2id(s_), t = id
0550: 67 65 6e 2e 76 32 69 64 28 74 5f 29 3b 0d 0a 09 gen.v2id(t_);...
0560: 09 47 5b 73 5d 2e 70 75 73 68 5f 62 61 63 6b 28 .G[s].push_back(
0570: 74 29 3b 0d 0a 09 09 47 5b 74 5d 2e 70 75 73 68 t);....G[t].push
0580: 5f 62 61 63 6b 28 73 29 3b 0d 0a 09 09 46 5b 73 _back(s);....F[s
0590: 5d 5b 74 5d 20 3d 20 66 3b 0d 0a 09 09 46 5b 74 ][t] = f;....F[t
05a0: 5d 5b 73 5d 20 3d 20 30 3b 0d 0a 09 7d 0d 0a 0d ][s] = 0;...}...
05b0: 0a 09 46 6c 6f 77 20 63 61 6c 63 28 20 56 65 72 ..Flow calc( Ver
05c0: 74 20 73 5f 2c 20 56 65 72 74 20 74 5f 20 29 0d t s_, Vert t_ ).
05d0: 0a 09 7b 0d 0a 09 09 63 6f 6e 73 74 20 69 6e 74 ..{....const int
05e0: 20 53 20 3d 20 69 64 67 65 6e 2e 76 32 69 64 28 S = idgen.v2id(
05f0: 73 5f 29 2c 20 44 20 3d 20 69 64 67 65 6e 2e 76 s_), D = idgen.v
0600: 32 69 64 28 74 5f 29 3b 0d 0a 09 09 66 6f 72 28 2id(t_);....for(
0610: 20 46 6c 6f 77 20 74 6f 74 61 6c 3d 30 20 3b 3b Flow total=0 ;;
0620: 20 29 20 7b 0d 0a 09 09 09 2f 2f 20 44 6f 20 42 ) {.....// Do B
0630: 46 53 20 61 6e 64 20 63 6f 6d 70 75 74 65 20 74 FS and compute t
0640: 68 65 20 6c 65 76 65 6c 20 66 6f 72 20 65 61 63 he level for eac
0650: 68 20 6e 6f 64 65 2e 0d 0a 09 09 09 69 6e 74 20 h node......int
0660: 4c 56 5b 4e 56 5d 20 3d 20 7b 30 7d 3b 0d 0a 09 LV[NV] = {0};...
0670: 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 51 28 ..vector<int> Q(
0680: 31 2c 20 53 29 3b 0d 0a 09 09 09 66 6f 72 28 69 1, S);.....for(i
0690: 6e 74 20 6c 76 3d 31 3b 20 21 51 2e 65 6d 70 74 nt lv=1; !Q.empt
06a0: 79 28 29 3b 20 2b 2b 6c 76 29 20 7b 0d 0a 09 09 y(); ++lv) {....
06b0: 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 51 32 ..vector<int> Q2
06c0: 3b 0d 0a 09 09 09 09 66 6f 72 28 73 69 7a 65 5f ;......for(size_
06d0: 74 20 69 3d 30 3b 20 69 21 3d 51 2e 73 69 7a 65 t i=0; i!=Q.size
06e0: 28 29 3b 20 2b 2b 69 29 20 7b 0d 0a 09 09 09 09 (); ++i) {......
06f0: 09 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 69 6e .const vector<in
0700: 74 3e 26 20 6e 65 20 3d 20 47 5b 51 5b 69 5d 5d t>& ne = G[Q[i]]
0710: 3b 0d 0a 09 09 09 09 09 66 6f 72 28 73 69 7a 65 ;.......for(size
0720: 5f 74 20 6a 3d 30 3b 20 6a 21 3d 6e 65 2e 73 69 _t j=0; j!=ne.si
0730: 7a 65 28 29 3b 20 2b 2b 6a 29 0d 0a 09 09 09 09 ze(); ++j)......
0740: 09 09 69 66 28 20 46 5b 51 5b 69 5d 5d 5b 6e 65 ..if( F[Q[i]][ne
0750: 5b 6a 5d 5d 20 26 26 20 21 4c 56 5b 6e 65 5b 6a [j]] && !LV[ne[j
0760: 5d 5d 20 26 26 20 6e 65 5b 6a 5d 21 3d 53 20 29 ]] && ne[j]!=S )
0770: 0d 0a 09 09 09 09 09 09 09 4c 56 5b 6e 65 5b 6a .........LV[ne[j
0780: 5d 5d 3d 6c 76 2c 20 51 32 2e 70 75 73 68 5f 62 ]]=lv, Q2.push_b
0790: 61 63 6b 28 6e 65 5b 6a 5d 29 3b 0d 0a 09 09 09 ack(ne[j]);.....
07a0: 09 7d 0d 0a 09 09 09 09 51 2e 73 77 61 70 28 51 .}......Q.swap(Q
07b0: 32 29 3b 0d 0a 09 09 09 7d 0d 0a 0d 0a 09 09 09 2);.....}.......
07c0: 2f 2f 20 44 65 73 74 69 6e 61 74 69 6f 6e 20 69 // Destination i
07d0: 73 20 6e 6f 77 20 75 6e 72 65 61 63 68 61 62 6c s now unreachabl
07e0: 65 2e 20 44 6f 6e 65 2e 0d 0a 09 09 09 69 66 28 e. Done......if(
07f0: 20 21 4c 56 5b 44 5d 20 29 0d 0a 09 09 09 09 72 !LV[D] )......r
0800: 65 74 75 72 6e 20 74 6f 74 61 6c 3b 0d 0a 0d 0a eturn total;....
0810: 09 09 09 2f 2f 20 49 74 65 72 61 74 69 6e 67 20 ...// Iterating
0820: 44 46 53 2e 0d 0a 09 09 09 62 6f 6f 6c 20 62 6c DFS......bool bl
0830: 6f 63 6b 65 64 5b 4e 56 5d 20 3d 20 7b 7d 3b 0d ocked[NV] = {};.
0840: 0a 09 09 09 74 6f 74 61 6c 20 2b 3d 20 64 69 6e ....total += din
0850: 69 63 5f 64 66 73 28 20 53 2c 20 44 2c 20 4c 56 ic_dfs( S, D, LV
0860: 2c 20 30 78 37 66 66 66 66 66 66 66 2c 20 62 6c , 0x7fffffff, bl
0870: 6f 63 6b 65 64 20 29 3b 0d 0a 09 09 7d 0d 0a 09 ocked );....}...
0880: 7d 0d 0a 0d 0a 70 72 69 76 61 74 65 3a 0d 0a 09 }....private:...
0890: 46 6c 6f 77 20 64 69 6e 69 63 5f 64 66 73 28 20 Flow dinic_dfs(
08a0: 69 6e 74 20 76 2c 20 69 6e 74 20 44 2c 20 69 6e int v, int D, in
08b0: 74 20 4c 56 5b 5d 2c 20 46 6c 6f 77 20 66 6c 6f t LV[], Flow flo
08c0: 77 5f 69 6e 2c 20 62 6f 6f 6c 20 62 6c 6f 63 6b w_in, bool block
08d0: 65 64 5b 5d 20 29 0d 0a 09 7b 0d 0a 09 09 46 6c ed[] )...{....Fl
08e0: 6f 77 20 66 6c 6f 77 5f 6f 75 74 20 3d 20 30 3b ow flow_out = 0;
08f0: 0d 0a 09 09 66 6f 72 28 73 69 7a 65 5f 74 20 69 ....for(size_t i
0900: 3d 30 3b 20 69 21 3d 47 5b 76 5d 2e 73 69 7a 65 =0; i!=G[v].size
0910: 28 29 3b 20 2b 2b 69 29 20 7b 0d 0a 09 09 09 69 (); ++i) {.....i
0920: 6e 74 20 75 20 3d 20 47 5b 76 5d 5b 69 5d 3b 0d nt u = G[v][i];.
0930: 0a 09 09 09 69 66 28 20 4c 56 5b 76 5d 2b 31 3d ....if( LV[v]+1=
0940: 3d 4c 56 5b 75 5d 20 26 26 20 46 5b 76 5d 5b 75 =LV[u] && F[v][u
0950: 5d 20 29 20 7b 0d 0a 09 09 09 09 46 6c 6f 77 20 ] ) {......Flow
0960: 66 20 3d 20 6d 69 6e 28 66 6c 6f 77 5f 69 6e 2d f = min(flow_in-
0970: 66 6c 6f 77 5f 6f 75 74 2c 20 46 5b 76 5d 5b 75 flow_out, F[v][u
0980: 5d 29 3b 0d 0a 09 09 09 09 69 66 28 20 75 3d 3d ]);......if( u==
0990: 44 20 7c 7c 20 21 62 6c 6f 63 6b 65 64 5b 75 5d D || !blocked[u]
09a0: 20 26 26 20 28 66 3d 64 69 6e 69 63 5f 64 66 73 && (f=dinic_dfs
09b0: 28 75 2c 44 2c 4c 56 2c 66 2c 62 6c 6f 63 6b 65 (u,D,LV,f,blocke
09c0: 64 29 29 3e 30 20 29 20 7b 0d 0a 09 09 09 09 09 d))>0 ) {.......
09d0: 46 5b 76 5d 5b 75 5d 20 20 2d 3d 20 66 3b 0d 0a F[v][u] -= f;..
09e0: 09 09 09 09 09 46 5b 75 5d 5b 76 5d 20 20 2b 3d .....F[u][v] +=
09f0: 20 66 3b 0d 0a 09 09 09 09 09 66 6c 6f 77 5f 6f f;.......flow_o
0a00: 75 74 20 2b 3d 20 66 3b 0d 0a 09 09 09 09 09 69 ut += f;.......i
0a10: 66 28 20 66 6c 6f 77 5f 69 6e 20 3d 3d 20 66 6c f( flow_in == fl
0a20: 6f 77 5f 6f 75 74 20 29 20 72 65 74 75 72 6e 20 ow_out ) return
0a30: 66 6c 6f 77 5f 6f 75 74 3b 0d 0a 09 09 09 09 7d flow_out;......}
0a40: 0d 0a 09 09 09 7d 0d 0a 09 09 7d 0d 0a 09 09 62 .....}....}....b
0a50: 6c 6f 63 6b 65 64 5b 76 5d 20 3d 20 28 66 6c 6f locked[v] = (flo
0a60: 77 5f 6f 75 74 3d 3d 30 29 3b 0d 0a 09 09 72 65 w_out==0);....re
0a70: 74 75 72 6e 20 66 6c 6f 77 5f 6f 75 74 3b 0d 0a turn flow_out;..
0a80: 09 7d 0d 0a 7d 3b 0d 0a 0d 0a 63 6c 61 73 73 20 .}..};....class
0a90: 46 6f 78 41 6e 64 43 61 6b 65 20 7b 20 70 75 62 FoxAndCake { pub
0aa0: 6c 69 63 3a 0d 0a 09 73 74 72 69 6e 67 20 61 62 lic:...string ab
0ab0: 6c 65 54 6f 44 69 76 69 64 65 28 69 6e 74 20 57 leToDivide(int W
0ac0: 2c 20 69 6e 74 20 48 2c 20 76 65 63 74 6f 72 20 , int H, vector
0ad0: 3c 69 6e 74 3e 20 78 2c 20 76 65 63 74 6f 72 20 <int> x, vector
0ae0: 3c 69 6e 74 3e 20 79 29 0d 0a 09 7b 0d 0a 09 09 <int> y)...{....
0af0: 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 63 vector< vector<c
0b00: 68 61 72 3e 20 3e 20 4d 20 3d 20 63 6f 6d 70 72 har> > M = compr
0b10: 65 73 73 28 57 2c 20 48 2c 20 78 2c 20 79 29 3b ess(W, H, x, y);
0b20: 0d 0a 09 09 48 20 3d 20 4d 2e 73 69 7a 65 28 29 ....H = M.size()
0b30: 3b 0d 0a 09 09 57 20 3d 20 4d 5b 30 5d 2e 73 69 ;....W = M[0].si
0b40: 7a 65 28 29 3b 0d 0a 0d 0a 09 09 74 79 70 65 64 ze();......typed
0b50: 65 66 20 70 61 69 72 3c 20 69 6e 74 2c 20 70 61 ef pair< int, pa
0b60: 69 72 3c 69 6e 74 2c 69 6e 74 3e 20 3e 20 56 65 ir<int,int> > Ve
0b70: 72 74 3b 0d 0a 09 09 65 6e 75 6d 20 7b 49 4e 2c rt;....enum {IN,
0b80: 20 4f 55 54 2c 20 53 50 45 43 49 41 4c 7d 3b 0d OUT, SPECIAL};.
0b90: 0a 09 09 56 65 72 74 20 53 72 63 28 53 50 45 43 ...Vert Src(SPEC
0ba0: 49 41 4c 2c 20 6d 61 6b 65 5f 70 61 69 72 28 30 IAL, make_pair(0
0bb0: 2c 20 30 29 29 3b 0d 0a 09 09 56 65 72 74 20 53 , 0));....Vert S
0bc0: 69 6e 6b 28 53 50 45 43 49 41 4c 2c 20 6d 61 6b ink(SPECIAL, mak
0bd0: 65 5f 70 61 69 72 28 31 2c 20 31 29 29 3b 0d 0a e_pair(1, 1));..
0be0: 0d 0a 09 09 4d 61 78 46 6c 6f 77 3c 56 65 72 74 ....MaxFlow<Vert
0bf0: 2c 69 6e 74 2c 37 2a 37 2a 37 2a 32 2b 32 3e 20 ,int,7*7*7*2+2>
0c00: 47 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 20 79 3d G;....for(int y=
0c10: 30 3b 20 79 3c 48 3b 20 2b 2b 79 29 0d 0a 09 09 0; y<H; ++y)....
0c20: 66 6f 72 28 69 6e 74 20 78 3d 30 3b 20 78 3c 57 for(int x=0; x<W
0c30: 3b 20 2b 2b 78 29 20 69 66 28 20 4d 5b 79 5d 5b ; ++x) if( M[y][
0c40: 78 5d 21 3d 27 23 27 20 29 0d 0a 09 09 7b 0d 0a x]!='#' )....{..
0c50: 09 09 09 69 6e 74 20 64 79 5b 5d 20 3d 20 7b 2d ...int dy[] = {-
0c60: 31 2c 2b 31 2c 30 2c 30 7d 3b 0d 0a 09 09 09 69 1,+1,0,0};.....i
0c70: 6e 74 20 64 78 5b 5d 20 3d 20 7b 30 2c 30 2c 2d nt dx[] = {0,0,-
0c80: 31 2c 2b 31 7d 3b 0d 0a 09 09 09 66 6f 72 28 69 1,+1};.....for(i
0c90: 6e 74 20 64 3d 30 3b 20 64 3c 34 3b 20 2b 2b 64 nt d=0; d<4; ++d
0ca0: 29 20 7b 0d 0a 09 09 09 09 69 6e 74 20 79 79 20 ) {......int yy
0cb0: 3d 20 79 20 2b 20 64 79 5b 64 5d 3b 0d 0a 09 09 = y + dy[d];....
0cc0: 09 09 69 6e 74 20 78 78 20 3d 20 78 20 2b 20 64 ..int xx = x + d
0cd0: 78 5b 64 5d 3b 0d 0a 09 09 09 09 69 66 28 30 3c x[d];......if(0<
0ce0: 3d 79 79 26 26 79 79 3c 48 26 26 30 3c 3d 78 78 =yy&&yy<H&&0<=xx
0cf0: 26 26 78 78 3c 57 26 26 4d 5b 79 79 5d 5b 78 78 &&xx<W&&M[yy][xx
0d00: 5d 21 3d 27 23 27 29 0d 0a 09 09 09 09 09 47 2e ]!='#').......G.
0d10: 61 64 64 45 64 67 65 28 56 65 72 74 28 4f 55 54 addEdge(Vert(OUT
0d20: 2c 20 6d 61 6b 65 5f 70 61 69 72 28 79 2c 78 29 , make_pair(y,x)
0d30: 29 2c 20 56 65 72 74 28 49 4e 2c 20 6d 61 6b 65 ), Vert(IN, make
0d40: 5f 70 61 69 72 28 79 79 2c 78 78 29 29 2c 20 31 _pair(yy,xx)), 1
0d50: 29 3b 0d 0a 09 09 09 7d 0d 0a 0d 0a 09 09 09 47 );.....}.......G
0d60: 2e 61 64 64 45 64 67 65 28 56 65 72 74 28 49 4e .addEdge(Vert(IN
0d70: 2c 20 6d 61 6b 65 5f 70 61 69 72 28 79 2c 78 29 , make_pair(y,x)
0d80: 29 2c 20 56 65 72 74 28 4f 55 54 2c 20 6d 61 6b ), Vert(OUT, mak
0d90: 65 5f 70 61 69 72 28 79 2c 78 29 29 2c 20 31 29 e_pair(y,x)), 1)
0da0: 3b 0d 0a 09 09 09 69 66 28 4d 5b 79 5d 5b 78 5d ;.....if(M[y][x]
0db0: 3d 3d 27 43 27 29 20 47 2e 61 64 64 45 64 67 65 =='C') G.addEdge
0dc0: 28 53 72 63 2c 20 56 65 72 74 28 49 4e 2c 20 6d (Src, Vert(IN, m
0dd0: 61 6b 65 5f 70 61 69 72 28 79 2c 78 29 29 2c 20 ake_pair(y,x)),
0de0: 31 29 3b 0d 0a 09 09 09 69 66 28 4d 5b 79 5d 5b 1);.....if(M[y][
0df0: 78 5d 3d 3d 27 53 27 29 20 47 2e 61 64 64 45 64 x]=='S') G.addEd
0e00: 67 65 28 56 65 72 74 28 4f 55 54 2c 20 6d 61 6b ge(Vert(OUT, mak
0e10: 65 5f 70 61 69 72 28 79 2c 78 29 29 2c 20 53 69 e_pair(y,x)), Si
0e20: 6e 6b 2c 20 31 29 3b 0d 0a 09 09 7d 0d 0a 0d 0a nk, 1);....}....
0e30: 09 09 72 65 74 75 72 6e 20 47 2e 63 61 6c 63 28 ..return G.calc(
0e40: 53 72 63 2c 20 53 69 6e 6b 29 3d 3d 33 20 3f 20 Src, Sink)==3 ?
0e50: 22 59 65 73 22 20 3a 20 22 4e 6f 22 3b 0d 0a 09 "Yes" : "No";...
0e60: 7d 0d 0a 0d 0a 09 76 65 63 74 6f 72 3c 20 76 65 }.....vector< ve
0e70: 63 74 6f 72 3c 63 68 61 72 3e 20 3e 20 63 6f 6d ctor<char> > com
0e80: 70 72 65 73 73 28 69 6e 74 20 57 2c 20 69 6e 74 press(int W, int
0e90: 20 48 2c 20 76 65 63 74 6f 72 3c 69 6e 74 3e 26 H, vector<int>&
0ea0: 20 78 2c 20 76 65 63 74 6f 72 3c 69 6e 74 3e 26 x, vector<int>&
0eb0: 20 79 29 0d 0a 09 7b 0d 0a 09 09 66 6f 72 28 69 y)...{....for(i
0ec0: 6e 74 20 69 3d 30 3b 20 69 3c 37 3b 20 2b 2b 69 nt i=0; i<7; ++i
0ed0: 29 0d 0a 09 09 09 2d 2d 78 5b 69 5d 2c 20 2d 2d ).....--x[i], --
0ee0: 79 5b 69 5d 3b 0d 0a 0d 0a 09 09 73 65 74 3c 69 y[i];......set<i
0ef0: 6e 74 3e 20 73 69 67 78 2c 20 73 69 67 79 3b 0d nt> sigx, sigy;.
0f00: 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 ...for(int i=0;
0f10: 69 3c 37 3b 20 2b 2b 69 29 0d 0a 09 09 09 66 6f i<7; ++i).....fo
0f20: 72 28 69 6e 74 20 64 3d 2d 33 3b 20 64 3c 3d 2b r(int d=-3; d<=+
0f30: 33 3b 20 2b 2b 64 29 20 7b 0d 0a 09 09 09 09 69 3; ++d) {......i
0f40: 66 28 30 3c 3d 78 5b 69 5d 2b 64 20 26 26 20 78 f(0<=x[i]+d && x
0f50: 5b 69 5d 2b 64 3c 57 29 0d 0a 09 09 09 09 09 73 [i]+d<W).......s
0f60: 69 67 78 2e 69 6e 73 65 72 74 28 78 5b 69 5d 2b igx.insert(x[i]+
0f70: 64 29 3b 0d 0a 09 09 09 09 69 66 28 30 3c 3d 79 d);......if(0<=y
0f80: 5b 69 5d 2b 64 20 26 26 20 79 5b 69 5d 2b 64 3c [i]+d && y[i]+d<
0f90: 48 29 0d 0a 09 09 09 09 09 73 69 67 79 2e 69 6e H).......sigy.in
0fa0: 73 65 72 74 28 79 5b 69 5d 2b 64 29 3b 0d 0a 09 sert(y[i]+d);...
0fb0: 09 09 7d 0d 0a 09 09 76 65 63 74 6f 72 3c 69 6e ..}....vector<in
0fc0: 74 3e 20 73 78 28 73 69 67 78 2e 62 65 67 69 6e t> sx(sigx.begin
0fd0: 28 29 2c 20 73 69 67 78 2e 65 6e 64 28 29 29 3b (), sigx.end());
0fe0: 0d 0a 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 ....vector<int>
0ff0: 73 79 28 73 69 67 79 2e 62 65 67 69 6e 28 29 2c sy(sigy.begin(),
1000: 20 73 69 67 79 2e 65 6e 64 28 29 29 3b 0d 0a 09 sigy.end());...
1010: 09 6d 61 70 3c 69 6e 74 2c 69 6e 74 3e 20 69 6e .map<int,int> in
1020: 76 5f 73 78 3b 20 66 6f 72 28 69 6e 74 20 69 3d v_sx; for(int i=
1030: 30 3b 20 69 3c 73 78 2e 73 69 7a 65 28 29 3b 20 0; i<sx.size();
1040: 2b 2b 69 29 20 69 6e 76 5f 73 78 5b 73 78 5b 69 ++i) inv_sx[sx[i
1050: 5d 5d 20 3d 20 69 3b 0d 0a 09 09 6d 61 70 3c 69 ]] = i;....map<i
1060: 6e 74 2c 69 6e 74 3e 20 69 6e 76 5f 73 79 3b 20 nt,int> inv_sy;
1070: 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 73 for(int i=0; i<s
1080: 79 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 20 69 y.size(); ++i) i
1090: 6e 76 5f 73 79 5b 73 79 5b 69 5d 5d 20 3d 20 69 nv_sy[sy[i]] = i
10a0: 3b 0d 0a 09 09 57 20 3d 20 73 78 2e 73 69 7a 65 ;....W = sx.size
10b0: 28 29 3b 0d 0a 09 09 48 20 3d 20 73 79 2e 73 69 ();....H = sy.si
10c0: 7a 65 28 29 3b 0d 0a 0d 0a 09 09 76 65 63 74 6f ze();......vecto
10d0: 72 3c 20 76 65 63 74 6f 72 3c 63 68 61 72 3e 20 r< vector<char>
10e0: 3e 20 72 65 73 75 6c 74 28 48 2c 20 76 65 63 74 > result(H, vect
10f0: 6f 72 3c 63 68 61 72 3e 28 57 2c 20 27 20 27 29 or<char>(W, ' ')
1100: 29 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d );....for(int i=
1110: 30 3b 20 69 3c 37 3b 20 2b 2b 69 29 20 7b 0d 0a 0; i<7; ++i) {..
1120: 09 09 09 69 6e 74 20 78 78 20 3d 20 69 6e 76 5f ...int xx = inv_
1130: 73 78 5b 78 5b 69 5d 5d 3b 0d 0a 09 09 09 69 6e sx[x[i]];.....in
1140: 74 20 79 79 20 3d 20 69 6e 76 5f 73 79 5b 79 5b t yy = inv_sy[y[
1150: 69 5d 5d 3b 0d 0a 09 09 09 72 65 73 75 6c 74 5b i]];.....result[
1160: 79 79 5d 5b 78 78 5d 20 3d 20 28 69 3d 3d 30 3f yy][xx] = (i==0?
1170: 27 23 27 3a 69 3c 34 3f 27 43 27 3a 27 53 27 29 '#':i<4?'C':'S')
1180: 3b 0d 0a 09 09 7d 0d 0a 09 09 72 65 74 75 72 6e ;....}....return
1190: 20 72 65 73 75 6c 74 3b 0d 0a 09 7d 0d 0a 0d 0a result;...}....
11a0: 7d 3b 0d 0a 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 };....// BEGIN C
11b0: 55 54 20 48 45 52 45 0d 0a 23 69 6e 63 6c 75 64 UT HERE..#includ
11c0: 65 20 3c 63 74 69 6d 65 3e 0d 0a 64 6f 75 62 6c e <ctime>..doubl
11d0: 65 20 73 74 61 72 74 5f 74 69 6d 65 3b 20 73 74 e start_time; st
11e0: 72 69 6e 67 20 74 69 6d 65 72 28 29 0d 0a 20 7b ring timer().. {
11f0: 20 6f 73 74 72 69 6e 67 73 74 72 65 61 6d 20 6f ostringstream o
1200: 73 3b 20 6f 73 20 3c 3c 20 22 20 28 22 20 3c 3c s; os << " (" <<
1210: 20 69 6e 74 28 28 63 6c 6f 63 6b 28 29 2d 73 74 int((clock()-st
1220: 61 72 74 5f 74 69 6d 65 29 2f 43 4c 4f 43 4b 53 art_time)/CLOCKS
1230: 5f 50 45 52 5f 53 45 43 2a 31 30 30 30 29 20 3c _PER_SEC*1000) <
1240: 3c 20 22 20 6d 73 65 63 29 22 3b 20 72 65 74 75 < " msec)"; retu
1250: 72 6e 20 6f 73 2e 73 74 72 28 29 3b 20 7d 0d 0a rn os.str(); }..
1260: 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d template<typenam
1270: 65 20 54 3e 20 6f 73 74 72 65 61 6d 26 20 6f 70 e T> ostream& op
1280: 65 72 61 74 6f 72 3c 3c 28 6f 73 74 72 65 61 6d erator<<(ostream
1290: 26 20 6f 73 2c 20 63 6f 6e 73 74 20 76 65 63 74 & os, const vect
12a0: 6f 72 3c 54 3e 26 20 76 29 0d 0a 20 7b 20 6f 73 or<T>& v).. { os
12b0: 20 3c 3c 20 22 7b 20 22 3b 0d 0a 20 20 20 66 6f << "{ ";.. fo
12c0: 72 28 74 79 70 65 6e 61 6d 65 20 76 65 63 74 6f r(typename vecto
12d0: 72 3c 54 3e 3a 3a 63 6f 6e 73 74 5f 69 74 65 72 r<T>::const_iter
12e0: 61 74 6f 72 20 69 74 3d 76 2e 62 65 67 69 6e 28 ator it=v.begin(
12f0: 29 3b 20 69 74 21 3d 76 2e 65 6e 64 28 29 3b 20 ); it!=v.end();
1300: 2b 2b 69 74 29 0d 0a 20 20 20 6f 73 20 3c 3c 20 ++it).. os <<
1310: 27 5c 22 27 20 3c 3c 20 2a 69 74 20 3c 3c 20 27 '\"' << *it << '
1320: 5c 22 27 20 3c 3c 20 28 69 74 2b 31 3d 3d 76 2e \"' << (it+1==v.
1330: 65 6e 64 28 29 20 3f 20 22 22 20 3a 20 22 2c 20 end() ? "" : ",
1340: 22 29 3b 20 6f 73 20 3c 3c 20 22 20 7d 22 3b 20 "); os << " }";
1350: 72 65 74 75 72 6e 20 6f 73 3b 20 7d 0d 0a 76 6f return os; }..vo
1360: 69 64 20 76 65 72 69 66 79 5f 63 61 73 65 28 63 id verify_case(c
1370: 6f 6e 73 74 20 73 74 72 69 6e 67 26 20 45 78 70 onst string& Exp
1380: 65 63 74 65 64 2c 20 63 6f 6e 73 74 20 73 74 72 ected, const str
1390: 69 6e 67 26 20 52 65 63 65 69 76 65 64 29 20 7b ing& Received) {
13a0: 0d 0a 20 62 6f 6f 6c 20 6f 6b 20 3d 20 28 45 78 .. bool ok = (Ex
13b0: 70 65 63 74 65 64 20 3d 3d 20 52 65 63 65 69 76 pected == Receiv
13c0: 65 64 29 3b 0d 0a 20 69 66 28 6f 6b 29 20 63 65 ed);.. if(ok) ce
13d0: 72 72 20 3c 3c 20 22 50 41 53 53 45 44 22 20 3c rr << "PASSED" <
13e0: 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 6e 64 < timer() << end
13f0: 6c 3b 20 20 65 6c 73 65 20 7b 20 63 65 72 72 20 l; else { cerr
1400: 3c 3c 20 22 46 41 49 4c 45 44 22 20 3c 3c 20 74 << "FAILED" << t
1410: 69 6d 65 72 28 29 20 3c 3c 20 65 6e 64 6c 3b 0d imer() << endl;.
1420: 0a 20 63 65 72 72 20 3c 3c 20 22 5c 74 6f 3a 20 . cerr << "\to:
1430: 5c 22 22 20 3c 3c 20 45 78 70 65 63 74 65 64 20 \"" << Expected
1440: 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 20 << '\"' << endl
1450: 3c 3c 20 22 5c 74 78 3a 20 5c 22 22 20 3c 3c 20 << "\tx: \"" <<
1460: 52 65 63 65 69 76 65 64 20 3c 3c 20 27 5c 22 27 Received << '\"'
1470: 20 3c 3c 20 65 6e 64 6c 3b 20 7d 20 7d 0d 0a 23 << endl; } }..#
1480: 64 65 66 69 6e 65 20 43 41 53 45 28 4e 29 20 7b define CASE(N) {
1490: 63 65 72 72 20 3c 3c 20 22 54 65 73 74 20 43 61 cerr << "Test Ca
14a0: 73 65 20 23 22 20 3c 3c 20 4e 20 3c 3c 20 22 2e se #" << N << ".
14b0: 2e 2e 22 20 3c 3c 20 66 6c 75 73 68 3b 20 73 74 .." << flush; st
14c0: 61 72 74 5f 74 69 6d 65 3d 63 6c 6f 63 6b 28 29 art_time=clock()
14d0: 3b 0d 0a 23 64 65 66 69 6e 65 20 45 4e 44 09 20 ;..#define END.
14e0: 76 65 72 69 66 79 5f 63 61 73 65 28 5f 2c 20 46 verify_case(_, F
14f0: 6f 78 41 6e 64 43 61 6b 65 28 29 2e 61 62 6c 65 oxAndCake().able
1500: 54 6f 44 69 76 69 64 65 28 6e 2c 20 6d 2c 20 78 ToDivide(n, m, x
1510: 2c 20 79 29 29 3b 7d 0d 0a 69 6e 74 20 6d 61 69 , y));}..int mai
1520: 6e 28 29 7b 0d 0a 0d 0a 43 41 53 45 28 30 29 0d n(){....CASE(0).
1530: 0a 09 69 6e 74 20 6e 20 3d 20 32 3b 20 0d 0a 09 ..int n = 2; ...
1540: 69 6e 74 20 6d 20 3d 20 34 3b 20 0d 0a 09 69 6e int m = 4; ...in
1550: 74 20 78 5f 5b 5d 20 3d 20 7b 31 2c 31 2c 31 2c t x_[] = {1,1,1,
1560: 31 2c 32 2c 32 2c 32 7d 3b 0d 0a 09 20 20 76 65 1,2,2,2};... ve
1570: 63 74 6f 72 20 3c 69 6e 74 3e 20 78 28 78 5f 2c ctor <int> x(x_,
1580: 20 78 5f 2b 73 69 7a 65 6f 66 28 78 5f 29 2f 73 x_+sizeof(x_)/s
1590: 69 7a 65 6f 66 28 2a 78 5f 29 29 3b 20 0d 0a 09 izeof(*x_)); ...
15a0: 69 6e 74 20 79 5f 5b 5d 20 3d 20 7b 31 2c 32 2c int y_[] = {1,2,
15b0: 33 2c 34 2c 32 2c 33 2c 34 7d 3b 0d 0a 09 20 20 3,4,2,3,4};...
15c0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 79 28 79 vector <int> y(y
15d0: 5f 2c 20 79 5f 2b 73 69 7a 65 6f 66 28 79 5f 29 _, y_+sizeof(y_)
15e0: 2f 73 69 7a 65 6f 66 28 2a 79 5f 29 29 3b 20 0d /sizeof(*y_)); .
15f0: 0a 09 73 74 72 69 6e 67 20 5f 20 3d 20 22 59 65 ..string _ = "Ye
1600: 73 22 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 s"; ..END..CASE(
1610: 31 29 0d 0a 09 69 6e 74 20 6e 20 3d 20 32 3b 20 1)...int n = 2;
1620: 0d 0a 09 69 6e 74 20 6d 20 3d 20 34 3b 20 0d 0a ...int m = 4; ..
1630: 09 69 6e 74 20 78 5f 5b 5d 20 3d 20 7b 31 2c 31 .int x_[] = {1,1
1640: 2c 32 2c 31 2c 32 2c 31 2c 32 7d 3b 0d 0a 09 20 ,2,1,2,1,2};...
1650: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 78 28 vector <int> x(
1660: 78 5f 2c 20 78 5f 2b 73 69 7a 65 6f 66 28 78 5f x_, x_+sizeof(x_
1670: 29 2f 73 69 7a 65 6f 66 28 2a 78 5f 29 29 3b 20 )/sizeof(*x_));
1680: 0d 0a 09 69 6e 74 20 79 5f 5b 5d 20 3d 20 7b 31 ...int y_[] = {1
1690: 2c 32 2c 32 2c 33 2c 33 2c 34 2c 34 7d 3b 0d 0a ,2,2,3,3,4,4};..
16a0: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
16b0: 79 28 79 5f 2c 20 79 5f 2b 73 69 7a 65 6f 66 28 y(y_, y_+sizeof(
16c0: 79 5f 29 2f 73 69 7a 65 6f 66 28 2a 79 5f 29 29 y_)/sizeof(*y_))
16d0: 3b 20 0d 0a 09 73 74 72 69 6e 67 20 5f 20 3d 20 ; ...string _ =
16e0: 22 4e 6f 22 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 "No"; ..END..CAS
16f0: 45 28 32 29 0d 0a 09 69 6e 74 20 6e 20 3d 20 36 E(2)...int n = 6
1700: 3b 20 0d 0a 09 69 6e 74 20 6d 20 3d 20 36 3b 20 ; ...int m = 6;
1710: 0d 0a 09 69 6e 74 20 78 5f 5b 5d 20 3d 20 7b 31 ...int x_[] = {1
1720: 2c 31 2c 33 2c 34 2c 33 2c 34 2c 35 7d 3b 0d 0a ,1,3,4,3,4,5};..
1730: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
1740: 78 28 78 5f 2c 20 78 5f 2b 73 69 7a 65 6f 66 28 x(x_, x_+sizeof(
1750: 78 5f 29 2f 73 69 7a 65 6f 66 28 2a 78 5f 29 29 x_)/sizeof(*x_))
1760: 3b 20 0d 0a 09 69 6e 74 20 79 5f 5b 5d 20 3d 20 ; ...int y_[] =
1770: 7b 32 2c 36 2c 34 2c 35 2c 35 2c 34 2c 32 7d 3b {2,6,4,5,5,4,2};
1780: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
1790: 3e 20 79 28 79 5f 2c 20 79 5f 2b 73 69 7a 65 6f > y(y_, y_+sizeo
17a0: 66 28 79 5f 29 2f 73 69 7a 65 6f 66 28 2a 79 5f f(y_)/sizeof(*y_
17b0: 29 29 3b 20 0d 0a 09 73 74 72 69 6e 67 20 5f 20 )); ...string _
17c0: 3d 20 22 59 65 73 22 3b 20 0d 0a 45 4e 44 0d 0a = "Yes"; ..END..
17d0: 43 41 53 45 28 33 29 0d 0a 09 69 6e 74 20 6e 20 CASE(3)...int n
17e0: 3d 20 39 39 39 39 39 39 39 39 39 3b 20 0d 0a 09 = 999999999; ...
17f0: 69 6e 74 20 6d 20 3d 20 39 39 39 39 39 39 39 39 int m = 99999999
1800: 39 3b 20 0d 0a 09 69 6e 74 20 78 5f 5b 5d 20 3d 9; ...int x_[] =
1810: 20 7b 35 30 30 30 30 30 30 30 30 2c 31 2c 31 2c {500000000,1,1,
1820: 31 2c 39 39 39 39 39 39 39 39 39 2c 39 39 39 39 1,999999999,9999
1830: 39 39 39 39 39 2c 39 39 39 39 39 39 39 39 39 7d 99999,999999999}
1840: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
1850: 74 3e 20 78 28 78 5f 2c 20 78 5f 2b 73 69 7a 65 t> x(x_, x_+size
1860: 6f 66 28 78 5f 29 2f 73 69 7a 65 6f 66 28 2a 78 of(x_)/sizeof(*x
1870: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 79 5f 5b 5d _)); ...int y_[]
1880: 20 3d 20 7b 35 30 30 30 30 30 30 30 30 2c 31 2c = {500000000,1,
1890: 32 2c 33 2c 39 39 39 39 39 39 39 39 37 2c 39 39 2,3,999999997,99
18a0: 39 39 39 39 39 39 38 2c 39 39 39 39 39 39 39 39 9999998,99999999
18b0: 39 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 9};... vector <
18c0: 69 6e 74 3e 20 79 28 79 5f 2c 20 79 5f 2b 73 69 int> y(y_, y_+si
18d0: 7a 65 6f 66 28 79 5f 29 2f 73 69 7a 65 6f 66 28 zeof(y_)/sizeof(
18e0: 2a 79 5f 29 29 3b 20 0d 0a 09 73 74 72 69 6e 67 *y_)); ...string
18f0: 20 5f 20 3d 20 22 59 65 73 22 3b 20 0d 0a 45 4e _ = "Yes"; ..EN
1900: 44 0d 0a 43 41 53 45 28 34 29 0d 0a 09 69 6e 74 D..CASE(4)...int
1910: 20 6e 20 3d 20 31 30 30 30 30 30 30 30 30 30 3b n = 1000000000;
1920: 20 0d 0a 09 69 6e 74 20 6d 20 3d 20 31 30 30 30 ...int m = 1000
1930: 30 30 30 30 30 30 3b 20 0d 0a 09 69 6e 74 20 78 000000; ...int x
1940: 5f 5b 5d 20 3d 20 7b 35 30 30 30 30 30 30 30 30 _[] = {500000000
1950: 2c 31 2c 31 2c 32 2c 39 39 39 39 39 39 39 39 38 ,1,1,2,999999998
1960: 2c 39 39 39 39 39 39 39 39 39 2c 39 39 39 39 39 ,999999999,99999
1970: 39 39 39 39 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 9999};... vecto
1980: 72 20 3c 69 6e 74 3e 20 78 28 78 5f 2c 20 78 5f r <int> x(x_, x_
1990: 2b 73 69 7a 65 6f 66 28 78 5f 29 2f 73 69 7a 65 +sizeof(x_)/size
19a0: 6f 66 28 2a 78 5f 29 29 3b 20 0d 0a 09 69 6e 74 of(*x_)); ...int
19b0: 20 79 5f 5b 5d 20 3d 20 7b 35 30 30 30 30 30 30 y_[] = {5000000
19c0: 30 30 2c 31 2c 32 2c 31 2c 39 39 39 39 39 39 39 00,1,2,1,9999999
19d0: 39 39 2c 39 39 39 39 39 39 39 39 38 2c 39 39 39 99,999999998,999
19e0: 39 39 39 39 39 39 7d 3b 0d 0a 09 20 20 76 65 63 999999};... vec
19f0: 74 6f 72 20 3c 69 6e 74 3e 20 79 28 79 5f 2c 20 tor <int> y(y_,
1a00: 79 5f 2b 73 69 7a 65 6f 66 28 79 5f 29 2f 73 69 y_+sizeof(y_)/si
1a10: 7a 65 6f 66 28 2a 79 5f 29 29 3b 20 0d 0a 09 73 zeof(*y_)); ...s
1a20: 74 72 69 6e 67 20 5f 20 3d 20 22 4e 6f 22 3b 20 tring _ = "No";
1a30: 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 35 29 0d 0a ..END..CASE(5)..
1a40: 09 69 6e 74 20 6e 20 3d 20 37 3b 20 0d 0a 09 69 .int n = 7; ...i
1a50: 6e 74 20 6d 20 3d 20 32 3b 20 0d 0a 09 69 6e 74 nt m = 2; ...int
1a60: 20 78 5f 5b 5d 20 3d 20 7b 34 2c 31 2c 32 2c 33 x_[] = {4,1,2,3
1a70: 2c 35 2c 36 2c 37 7d 3b 0d 0a 09 20 20 76 65 63 ,5,6,7};... vec
1a80: 74 6f 72 20 3c 69 6e 74 3e 20 78 28 78 5f 2c 20 tor <int> x(x_,
1a90: 78 5f 2b 73 69 7a 65 6f 66 28 78 5f 29 2f 73 69 x_+sizeof(x_)/si
1aa0: 7a 65 6f 66 28 2a 78 5f 29 29 3b 20 0d 0a 09 69 zeof(*x_)); ...i
1ab0: 6e 74 20 79 5f 5b 5d 20 3d 20 7b 32 2c 31 2c 32 nt y_[] = {2,1,2
1ac0: 2c 32 2c 32 2c 32 2c 31 7d 3b 0d 0a 09 20 20 76 ,2,2,2,1};... v
1ad0: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 79 28 79 5f ector <int> y(y_
1ae0: 2c 20 79 5f 2b 73 69 7a 65 6f 66 28 79 5f 29 2f , y_+sizeof(y_)/
1af0: 73 69 7a 65 6f 66 28 2a 79 5f 29 29 3b 20 0d 0a sizeof(*y_)); ..
1b00: 09 73 74 72 69 6e 67 20 5f 20 3d 20 22 4e 6f 22 .string _ = "No"
1b10: 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 36 29 ; ..END..CASE(6)
1b20: 0d 0a 09 69 6e 74 20 6e 20 3d 20 37 3b 20 0d 0a ...int n = 7; ..
1b30: 09 69 6e 74 20 6d 20 3d 20 32 3b 20 0d 0a 09 69 .int m = 2; ...i
1b40: 6e 74 20 78 5f 5b 5d 20 3d 20 7b 35 2c 31 2c 32 nt x_[] = {5,1,2
1b50: 2c 34 2c 33 2c 36 2c 37 7d 3b 0d 0a 09 20 20 76 ,4,3,6,7};... v
1b60: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 78 28 78 5f ector <int> x(x_
1b70: 2c 20 78 5f 2b 73 69 7a 65 6f 66 28 78 5f 29 2f , x_+sizeof(x_)/
1b80: 73 69 7a 65 6f 66 28 2a 78 5f 29 29 3b 20 0d 0a sizeof(*x_)); ..
1b90: 09 20 20 69 6e 74 20 79 5f 5b 5d 20 3d 20 7b 31 . int y_[] = {1
1ba0: 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 7d 3b 0d 0a ,1,1,1,1,1,1};..
1bb0: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
1bc0: 79 28 79 5f 2c 20 79 5f 2b 73 69 7a 65 6f 66 28 y(y_, y_+sizeof(
1bd0: 79 5f 29 2f 73 69 7a 65 6f 66 28 2a 79 5f 29 29 y_)/sizeof(*y_))
1be0: 3b 20 0d 0a 09 73 74 72 69 6e 67 20 5f 20 3d 20 ; ...string _ =
1bf0: 22 4e 6f 22 3b 20 0d 0a 45 4e 44 0d 0a 7d 0d 0a "No"; ..END..}..
1c00: 2f 2f 20 45 4e 44 20 43 55 54 20 48 45 52 45 0d // END CUT HERE.
1c10: 0a .