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 63 6f 6d 70 ..#include <comp
00d0: 6c 65 78 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c lex>..#include <
00e0: 71 75 65 75 65 3e 0d 0a 23 69 6e 63 6c 75 64 65 queue>..#include
00f0: 20 3c 73 74 61 63 6b 3e 0d 0a 23 69 6e 63 6c 75 <stack>..#inclu
0100: 64 65 20 3c 63 6d 61 74 68 3e 0d 0a 75 73 69 6e de <cmath>..usin
0110: 67 20 6e 61 6d 65 73 70 61 63 65 20 73 74 64 3b g namespace std;
0120: 0d 0a 74 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c ..typedef long l
0130: 6f 6e 67 20 4c 4c 3b 0d 0a 0d 0a 4c 4c 20 6e 65 ong LL;....LL ne
0140: 78 74 5f 63 6f 6d 62 69 6e 61 74 69 6f 6e 28 4c xt_combination(L
0150: 4c 20 70 29 0d 0a 7b 0d 0a 09 4c 4c 20 6c 73 62 L p)..{...LL lsb
0160: 20 3d 20 70 20 26 20 2d 70 3b 0d 0a 09 4c 4c 20 = p & -p;...LL
0170: 72 65 6d 20 3d 20 70 20 2b 20 6c 73 62 3b 0d 0a rem = p + lsb;..
0180: 09 4c 4c 20 72 69 74 20 3d 20 72 65 6d 20 26 20 .LL rit = rem &
0190: 7e 70 3b 0d 0a 09 72 65 74 75 72 6e 20 72 65 6d ~p;...return rem
01a0: 7c 28 28 28 72 69 74 2f 6c 73 62 29 3e 3e 31 29 |(((rit/lsb)>>1)
01b0: 2d 31 29 3b 0d 0a 7d 0d 0a 0d 0a 63 6c 61 73 73 -1);..}....class
01c0: 20 42 79 74 65 4c 61 6e 64 0d 0a 7b 0d 0a 70 75 ByteLand..{..pu
01d0: 62 6c 69 63 3a 0d 0a 09 69 6e 74 20 62 75 69 6c blic:...int buil
01e0: 64 43 61 73 74 6c 65 73 28 76 65 63 74 6f 72 3c dCastles(vector<
01f0: 69 6e 74 3e 20 72 6f 61 64 2c 20 76 65 63 74 6f int> road, vecto
0200: 72 3c 69 6e 74 3e 20 64 69 73 74 61 6e 63 65 2c r<int> distance,
0210: 20 76 65 63 74 6f 72 3c 69 6e 74 3e 20 63 61 73 vector<int> cas
0220: 74 6c 65 2c 20 69 6e 74 20 6b 29 20 0d 0a 09 7b tle, int k) ...{
0230: 0d 0a 09 09 69 6e 74 20 6e 20 3d 20 72 6f 61 64 ....int n = road
0240: 2e 73 69 7a 65 28 29 3b 0d 0a 0d 0a 09 09 2f 2f .size();......//
0250: 20 43 6f 6e 73 74 72 75 63 74 20 74 68 65 20 47 Construct the G
0260: 72 61 70 68 0d 0a 09 09 69 6e 74 20 64 5b 35 30 raph....int d[50
0270: 5d 5b 35 30 5d 20 3d 20 7b 7d 3b 0d 0a 09 09 66 ][50] = {};....f
0280: 6f 72 28 69 6e 74 20 76 3d 30 3b 20 76 3c 6e 3b or(int v=0; v<n;
0290: 20 2b 2b 76 29 0d 0a 09 09 09 66 6f 72 28 69 6e ++v).....for(in
02a0: 74 20 75 3d 76 2b 31 3b 20 75 3c 6e 3b 20 2b 2b t u=v+1; u<n; ++
02b0: 75 29 0d 0a 09 09 09 09 64 5b 76 5d 5b 75 5d 20 u)......d[v][u]
02c0: 3d 20 64 5b 75 5d 5b 76 5d 20 3d 20 30 78 33 66 = d[u][v] = 0x3f
02d0: 66 66 66 66 66 66 3b 0d 0a 09 09 66 6f 72 28 69 ffffff;....for(i
02e0: 6e 74 20 76 3d 30 3b 20 76 3c 6e 3b 20 2b 2b 76 nt v=0; v<n; ++v
02f0: 29 0d 0a 09 09 09 64 5b 76 5d 5b 72 6f 61 64 5b ).....d[v][road[
0300: 76 5d 5d 20 3d 20 64 5b 72 6f 61 64 5b 76 5d 5d v]] = d[road[v]]
0310: 5b 76 5d 20 3d 20 6d 69 6e 28 20 64 5b 76 5d 5b [v] = min( d[v][
0320: 72 6f 61 64 5b 76 5d 5d 2c 20 64 69 73 74 61 6e road[v]], distan
0330: 63 65 5b 76 5d 20 29 3b 0d 0a 0d 0a 09 09 2f 2f ce[v] );......//
0340: 20 57 61 72 73 68 61 6c 6c 2d 46 6c 6f 79 64 0d Warshall-Floyd.
0350: 0a 09 09 66 6f 72 28 69 6e 74 20 6d 3d 30 3b 20 ...for(int m=0;
0360: 6d 3c 6e 3b 20 2b 2b 6d 29 0d 0a 09 09 09 66 6f m<n; ++m).....fo
0370: 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 6e 3b 20 r(int i=0; i<n;
0380: 2b 2b 69 29 0d 0a 09 09 09 09 66 6f 72 28 69 6e ++i)......for(in
0390: 74 20 6a 3d 30 3b 20 6a 3c 6e 3b 20 2b 2b 6a 29 t j=0; j<n; ++j)
03a0: 0d 0a 09 09 09 09 09 64 5b 69 5d 5b 6a 5d 20 3d .......d[i][j] =
03b0: 20 6d 69 6e 28 64 5b 69 5d 5b 6a 5d 2c 20 64 5b min(d[i][j], d[
03c0: 69 5d 5b 6d 5d 2b 64 5b 6d 5d 5b 6a 5d 29 3b 0d i][m]+d[m][j]);.
03d0: 0a 0d 0a 09 09 2f 2f 20 42 69 6e 61 72 79 20 53 .....// Binary S
03e0: 65 61 72 63 68 3a 20 74 68 65 20 61 6e 73 77 65 earch: the answe
03f0: 72 20 69 73 20 69 6e 20 28 4c 2c 52 5d 0d 0a 09 r is in (L,R]...
0400: 09 69 6e 74 20 4c 3d 2d 31 2c 20 52 3d 61 63 63 .int L=-1, R=acc
0410: 75 6d 75 6c 61 74 65 28 64 69 73 74 61 6e 63 65 umulate(distance
0420: 2e 62 65 67 69 6e 28 29 2c 20 64 69 73 74 61 6e .begin(), distan
0430: 63 65 2e 65 6e 64 28 29 2c 20 30 29 3b 0d 0a 09 ce.end(), 0);...
0440: 09 77 68 69 6c 65 28 20 52 2d 4c 20 3e 20 31 20 .while( R-L > 1
0450: 29 0d 0a 09 09 09 28 69 73 5f 70 6f 73 73 69 62 ).....(is_possib
0460: 6c 65 28 28 4c 2b 52 29 2f 32 2c 20 64 2c 20 6e le((L+R)/2, d, n
0470: 2c 20 63 61 73 74 6c 65 2c 20 6b 29 20 3f 20 52 , castle, k) ? R
0480: 20 3a 20 4c 29 20 3d 20 28 4c 2b 52 29 2f 32 3b : L) = (L+R)/2;
0490: 0d 0a 09 09 72 65 74 75 72 6e 20 52 3b 0d 0a 09 ....return R;...
04a0: 7d 0d 0a 0d 0a 09 62 6f 6f 6c 20 69 73 5f 70 6f }.....bool is_po
04b0: 73 73 69 62 6c 65 28 20 69 6e 74 20 44 2c 20 69 ssible( int D, i
04c0: 6e 74 20 64 5b 35 30 5d 5b 35 30 5d 2c 20 69 6e nt d[50][50], in
04d0: 74 20 6e 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f t n, const vecto
04e0: 72 3c 69 6e 74 3e 26 20 63 2c 20 69 6e 74 20 6b r<int>& c, int k
04f0: 20 29 0d 0a 09 7b 0d 0a 09 09 2f 2f 20 74 68 65 )...{....// the
0500: 20 73 65 74 20 6f 66 20 63 69 74 69 65 73 20 6e set of cities n
0510: 6f 74 20 63 6f 76 65 72 65 64 20 79 65 74 0d 0a ot covered yet..
0520: 09 09 4c 4c 20 67 6f 61 6c 20 3d 20 28 31 4c 4c ..LL goal = (1LL
0530: 20 3c 3c 20 6e 29 20 2d 20 31 3b 0d 0a 09 09 66 << n) - 1;....f
0540: 6f 72 28 69 6e 74 20 76 3d 30 3b 20 76 3c 6e 3b or(int v=0; v<n;
0550: 20 2b 2b 76 29 0d 0a 09 09 09 66 6f 72 28 69 6e ++v).....for(in
0560: 74 20 69 3d 30 3b 20 69 3c 63 2e 73 69 7a 65 28 t i=0; i<c.size(
0570: 29 3b 20 2b 2b 69 29 0d 0a 09 09 09 09 69 66 28 ); ++i)......if(
0580: 20 64 5b 76 5d 5b 63 5b 69 5d 5d 20 3c 3d 20 44 d[v][c[i]] <= D
0590: 20 29 0d 0a 09 09 09 09 09 67 6f 61 6c 20 26 3d ).......goal &=
05a0: 20 7e 28 31 4c 4c 20 3c 3c 20 76 29 3b 0d 0a 0d ~(1LL << v);...
05b0: 0a 09 09 2f 2f 20 74 68 65 20 73 65 74 20 6f 66 ...// the set of
05c0: 20 63 69 74 69 65 73 20 65 61 63 68 20 63 69 74 cities each cit
05d0: 79 20 63 61 6e 20 63 6f 76 65 72 0d 0a 09 09 73 y can cover....s
05e0: 65 74 3c 4c 4c 3e 20 6d 61 73 6b 3b 0d 0a 09 09 et<LL> mask;....
05f0: 66 6f 72 28 69 6e 74 20 76 3d 30 3b 20 76 3c 6e for(int v=0; v<n
0600: 3b 20 2b 2b 76 29 20 7b 0d 0a 09 09 09 4c 4c 20 ; ++v) {.....LL
0610: 6d 20 3d 20 30 3b 0d 0a 09 09 09 66 6f 72 28 69 m = 0;.....for(i
0620: 6e 74 20 75 3d 30 3b 20 75 3c 6e 3b 20 2b 2b 75 nt u=0; u<n; ++u
0630: 29 0d 0a 09 09 09 09 69 66 28 20 64 5b 76 5d 5b )......if( d[v][
0640: 75 5d 20 3c 3d 20 44 20 29 0d 0a 09 09 09 09 09 u] <= D ).......
0650: 6d 20 7c 3d 20 28 31 4c 4c 20 3c 3c 20 75 29 3b m |= (1LL << u);
0660: 0d 0a 09 09 09 69 66 28 20 6d 26 67 6f 61 6c 20 .....if( m&goal
0670: 29 0d 0a 09 09 09 09 6d 61 73 6b 2e 69 6e 73 65 )......mask.inse
0680: 72 74 28 20 6d 26 67 6f 61 6c 20 29 3b 0d 0a 09 rt( m&goal );...
0690: 09 7d 0d 0a 0d 0a 09 09 2f 2f 20 69 73 20 69 74 .}......// is it
06a0: 20 70 6f 73 73 69 62 6c 65 20 74 6f 20 63 6f 76 possible to cov
06b0: 65 72 20 74 68 65 20 67 6f 61 6c 20 62 79 20 61 er the goal by a
06c0: 74 20 6d 6f 73 74 20 6b 20 65 6c 65 6d 65 6e 74 t most k element
06d0: 73 20 66 72 6f 6d 20 6d 61 73 6b 3f 0d 0a 09 09 s from mask?....
06e0: 72 65 74 75 72 6e 20 63 61 6e 43 6f 76 65 72 28 return canCover(
06f0: 67 6f 61 6c 2c 20 6d 61 73 6b 2c 20 6b 29 3b 0d goal, mask, k);.
0700: 0a 09 7d 0d 0a 0d 0a 09 62 6f 6f 6c 20 63 61 6e ..}.....bool can
0710: 43 6f 76 65 72 28 20 4c 4c 20 67 6f 61 6c 2c 20 Cover( LL goal,
0720: 73 65 74 3c 4c 4c 3e 26 20 6d 61 73 6b 2c 20 69 set<LL>& mask, i
0730: 6e 74 20 6b 20 29 0d 0a 09 7b 0d 0a 09 09 2f 2f nt k )...{....//
0740: 20 6f 70 74 69 6d 69 7a 65 72 0d 0a 09 09 66 6f optimizer....fo
0750: 72 28 62 6f 6f 6c 20 75 70 64 61 74 65 3d 74 72 r(bool update=tr
0760: 75 65 3b 20 75 70 64 61 74 65 3b 20 29 20 7b 0d ue; update; ) {.
0770: 0a 09 09 09 75 70 64 61 74 65 20 3d 20 66 61 6c ....update = fal
0780: 73 65 3b 0d 0a 0d 0a 09 09 09 2f 2f 20 69 66 20 se;.......// if
0790: 2a 69 74 20 5c 73 75 62 73 65 74 65 71 20 2a 6a *it \subseteq *j
07a0: 74 20 66 6f 72 20 73 6f 6d 65 20 6a 74 2c 20 74 t for some jt, t
07b0: 68 65 6e 20 77 65 20 4e 45 56 45 52 20 75 73 65 hen we NEVER use
07c0: 20 69 74 0d 0a 09 09 09 2f 2f 20 69 66 20 2a 69 it.....// if *i
07d0: 74 20 69 73 20 74 68 65 20 6f 6e 6c 79 20 6d 61 t is the only ma
07e0: 73 6b 20 63 6f 76 65 72 69 6e 67 20 73 6f 6d 65 sk covering some
07f0: 20 63 69 74 79 2c 20 77 65 20 41 4c 57 41 59 53 city, we ALWAYS
0800: 20 75 73 65 20 69 74 0d 0a 09 09 09 66 6f 72 28 use it.....for(
0810: 73 65 74 3c 4c 4c 3e 3a 3a 69 74 65 72 61 74 6f set<LL>::iterato
0820: 72 20 69 74 3d 6d 61 73 6b 2e 62 65 67 69 6e 28 r it=mask.begin(
0830: 29 3b 20 69 74 21 3d 6d 61 73 6b 2e 65 6e 64 28 ); it!=mask.end(
0840: 29 3b 20 29 20 7b 0d 0a 09 09 09 09 62 6f 6f 6c ); ) {......bool
0850: 20 69 73 53 75 62 73 65 74 20 3d 20 66 61 6c 73 isSubset = fals
0860: 65 3b 0d 0a 09 09 09 09 4c 4c 20 20 20 6f 6e 6c e;......LL onl
0870: 79 42 79 4d 65 20 3d 20 2a 69 74 20 26 20 67 6f yByMe = *it & go
0880: 61 6c 3b 0d 0a 09 09 09 09 66 6f 72 28 73 65 74 al;......for(set
0890: 3c 4c 4c 3e 3a 3a 69 74 65 72 61 74 6f 72 20 6a <LL>::iterator j
08a0: 74 3d 6d 61 73 6b 2e 62 65 67 69 6e 28 29 3b 20 t=mask.begin();
08b0: 6a 74 21 3d 6d 61 73 6b 2e 65 6e 64 28 29 3b 20 jt!=mask.end();
08c0: 2b 2b 6a 74 29 0d 0a 09 09 09 09 09 69 66 28 20 ++jt).......if(
08d0: 69 74 21 3d 6a 74 20 29 20 7b 0d 0a 09 09 09 09 it!=jt ) {......
08e0: 09 09 6f 6e 6c 79 42 79 4d 65 20 26 3d 20 7e 2a ..onlyByMe &= ~*
08f0: 6a 74 3b 0d 0a 09 09 09 09 09 09 69 73 53 75 62 jt;........isSub
0900: 73 65 74 20 7c 3d 20 28 2a 69 74 20 26 20 2a 6a set |= (*it & *j
0910: 74 20 26 20 67 6f 61 6c 29 20 3d 3d 20 28 2a 69 t & goal) == (*i
0920: 74 20 26 20 67 6f 61 6c 29 3b 0d 0a 09 09 09 09 t & goal);......
0930: 09 7d 0d 0a 0d 0a 09 09 09 09 75 70 64 61 74 65 .}........update
0940: 20 7c 3d 20 69 73 53 75 62 73 65 74 20 7c 20 21 |= isSubset | !
0950: 21 6f 6e 6c 79 42 79 4d 65 3b 0d 0a 0d 0a 09 09 !onlyByMe;......
0960: 09 09 69 66 28 20 69 73 53 75 62 73 65 74 20 29 ..if( isSubset )
0970: 0d 0a 09 09 09 09 09 6d 61 73 6b 2e 65 72 61 73 .......mask.eras
0980: 65 28 69 74 2b 2b 29 3b 0d 0a 09 09 09 09 65 6c e(it++);......el
0990: 73 65 20 69 66 28 20 6f 6e 6c 79 42 79 4d 65 20 se if( onlyByMe
09a0: 29 20 7b 0d 0a 09 09 09 09 09 69 66 28 20 2d 2d ) {.......if( --
09b0: 6b 20 3c 20 30 20 29 0d 0a 09 09 09 09 09 09 72 k < 0 )........r
09c0: 65 74 75 72 6e 20 66 61 6c 73 65 3b 0d 0a 09 09 eturn false;....
09d0: 09 09 09 67 6f 61 6c 20 26 3d 20 7e 2a 69 74 3b ...goal &= ~*it;
09e0: 0d 0a 09 09 09 09 09 6d 61 73 6b 2e 65 72 61 73 .......mask.eras
09f0: 65 28 69 74 2b 2b 29 3b 0d 0a 09 09 09 09 7d 0d e(it++);......}.
0a00: 0a 09 09 09 09 65 6c 73 65 0d 0a 09 09 09 09 09 .....else.......
0a10: 2b 2b 69 74 3b 0d 0a 09 09 09 7d 0d 0a 0d 0a 09 ++it;.....}.....
0a20: 09 09 69 66 28 20 6d 61 73 6b 2e 73 69 7a 65 28 ..if( mask.size(
0a30: 29 3c 3d 6b 20 7c 7c 20 67 6f 61 6c 3d 3d 30 20 )<=k || goal==0
0a40: 29 0d 0a 09 09 09 09 72 65 74 75 72 6e 20 74 72 )......return tr
0a50: 75 65 3b 0d 0a 09 09 7d 0d 0a 0d 0a 09 09 2f 2f ue;....}......//
0a60: 20 65 78 68 61 75 73 74 69 76 65 20 73 65 61 72 exhaustive sear
0a70: 63 68 0d 0a 09 09 76 65 63 74 6f 72 3c 4c 4c 3e ch....vector<LL>
0a80: 20 6d 73 28 6d 61 73 6b 2e 62 65 67 69 6e 28 29 ms(mask.begin()
0a90: 2c 20 6d 61 73 6b 2e 65 6e 64 28 29 29 3b 0d 0a , mask.end());..
0aa0: 09 09 66 6f 72 28 4c 4c 20 69 3d 28 31 4c 4c 3c ..for(LL i=(1LL<
0ab0: 3c 6b 29 2d 31 3b 20 69 3c 28 31 4c 4c 3c 3c 6d <k)-1; i<(1LL<<m
0ac0: 73 2e 73 69 7a 65 28 29 29 3b 20 69 3d 6e 65 78 s.size()); i=nex
0ad0: 74 5f 63 6f 6d 62 69 6e 61 74 69 6f 6e 28 69 29 t_combination(i)
0ae0: 29 0d 0a 09 09 7b 0d 0a 09 09 09 4c 4c 20 67 67 )....{.....LL gg
0af0: 20 3d 20 67 6f 61 6c 3b 0d 0a 09 09 09 66 6f 72 = goal;.....for
0b00: 28 4c 4c 20 6a 3d 30 3b 20 28 31 4c 4c 3c 3c 6a (LL j=0; (1LL<<j
0b10: 29 3c 3d 69 3b 20 2b 2b 6a 29 0d 0a 09 09 09 09 )<=i; ++j)......
0b20: 69 66 28 20 69 20 26 20 28 31 3c 3c 6a 29 20 29 if( i & (1<<j) )
0b30: 0d 0a 09 09 09 09 09 67 67 20 26 3d 20 7e 6d 73 .......gg &= ~ms
0b40: 5b 6a 5d 3b 0d 0a 09 09 09 69 66 28 20 67 67 20 [j];.....if( gg
0b50: 3d 3d 20 30 20 29 0d 0a 09 09 09 09 72 65 74 75 == 0 )......retu
0b60: 72 6e 20 74 72 75 65 3b 0d 0a 09 09 7d 0d 0a 09 rn true;....}...
0b70: 09 72 65 74 75 72 6e 20 66 61 6c 73 65 3b 0d 0a .return false;..
0b80: 09 7d 0d 0a 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 .}....// BEGIN C
0b90: 55 54 20 48 45 52 45 0d 0a 09 70 75 62 6c 69 63 UT HERE...public
0ba0: 3a 0d 0a 09 76 6f 69 64 20 72 75 6e 5f 74 65 73 :...void run_tes
0bb0: 74 28 69 6e 74 20 43 61 73 65 29 20 7b 20 69 66 t(int Case) { if
0bc0: 20 28 28 43 61 73 65 20 3d 3d 20 2d 31 29 20 7c ((Case == -1) |
0bd0: 7c 20 28 43 61 73 65 20 3d 3d 20 30 29 29 20 74 | (Case == 0)) t
0be0: 65 73 74 5f 63 61 73 65 5f 30 28 29 3b 20 69 66 est_case_0(); if
0bf0: 20 28 28 43 61 73 65 20 3d 3d 20 2d 31 29 20 7c ((Case == -1) |
0c00: 7c 20 28 43 61 73 65 20 3d 3d 20 31 29 29 20 74 | (Case == 1)) t
0c10: 65 73 74 5f 63 61 73 65 5f 31 28 29 3b 20 69 66 est_case_1(); if
0c20: 20 28 28 43 61 73 65 20 3d 3d 20 2d 31 29 20 7c ((Case == -1) |
0c30: 7c 20 28 43 61 73 65 20 3d 3d 20 32 29 29 20 74 | (Case == 2)) t
0c40: 65 73 74 5f 63 61 73 65 5f 32 28 29 3b 20 69 66 est_case_2(); if
0c50: 20 28 28 43 61 73 65 20 3d 3d 20 2d 31 29 20 7c ((Case == -1) |
0c60: 7c 20 28 43 61 73 65 20 3d 3d 20 33 29 29 20 74 | (Case == 3)) t
0c70: 65 73 74 5f 63 61 73 65 5f 33 28 29 3b 20 69 66 est_case_3(); if
0c80: 20 28 28 43 61 73 65 20 3d 3d 20 2d 31 29 20 7c ((Case == -1) |
0c90: 7c 20 28 43 61 73 65 20 3d 3d 20 34 29 29 20 74 | (Case == 4)) t
0ca0: 65 73 74 5f 63 61 73 65 5f 34 28 29 3b 20 7d 0d est_case_4(); }.
0cb0: 0a 09 70 72 69 76 61 74 65 3a 0d 0a 09 74 65 6d ..private:...tem
0cc0: 70 6c 61 74 65 20 3c 74 79 70 65 6e 61 6d 65 20 plate <typename
0cd0: 54 3e 20 73 74 72 69 6e 67 20 70 72 69 6e 74 5f T> string print_
0ce0: 61 72 72 61 79 28 63 6f 6e 73 74 20 76 65 63 74 array(const vect
0cf0: 6f 72 3c 54 3e 20 26 56 29 20 7b 20 6f 73 74 72 or<T> &V) { ostr
0d00: 69 6e 67 73 74 72 65 61 6d 20 6f 73 3b 20 6f 73 ingstream os; os
0d10: 20 3c 3c 20 22 7b 20 22 3b 20 66 6f 72 20 28 74 << "{ "; for (t
0d20: 79 70 65 6e 61 6d 65 20 76 65 63 74 6f 72 3c 54 ypename vector<T
0d30: 3e 3a 3a 63 6f 6e 73 74 5f 69 74 65 72 61 74 6f >::const_iterato
0d40: 72 20 69 74 65 72 20 3d 20 56 2e 62 65 67 69 6e r iter = V.begin
0d50: 28 29 3b 20 69 74 65 72 20 21 3d 20 56 2e 65 6e (); iter != V.en
0d60: 64 28 29 3b 20 2b 2b 69 74 65 72 29 20 6f 73 20 d(); ++iter) os
0d70: 3c 3c 20 27 5c 22 27 20 3c 3c 20 2a 69 74 65 72 << '\"' << *iter
0d80: 20 3c 3c 20 22 5c 22 2c 22 3b 20 6f 73 20 3c 3c << "\","; os <<
0d90: 20 22 20 7d 22 3b 20 72 65 74 75 72 6e 20 6f 73 " }"; return os
0da0: 2e 73 74 72 28 29 3b 20 7d 0d 0a 09 76 6f 69 64 .str(); }...void
0db0: 20 76 65 72 69 66 79 5f 63 61 73 65 28 69 6e 74 verify_case(int
0dc0: 20 43 61 73 65 2c 20 63 6f 6e 73 74 20 69 6e 74 Case, const int
0dd0: 20 26 45 78 70 65 63 74 65 64 2c 20 63 6f 6e 73 &Expected, cons
0de0: 74 20 69 6e 74 20 26 52 65 63 65 69 76 65 64 29 t int &Received)
0df0: 20 7b 20 63 65 72 72 20 3c 3c 20 22 54 65 73 74 { cerr << "Test
0e00: 20 43 61 73 65 20 23 22 20 3c 3c 20 43 61 73 65 Case #" << Case
0e10: 20 3c 3c 20 22 2e 2e 2e 22 3b 20 69 66 20 28 45 << "..."; if (E
0e20: 78 70 65 63 74 65 64 20 3d 3d 20 52 65 63 65 69 xpected == Recei
0e30: 76 65 64 29 20 63 65 72 72 20 3c 3c 20 22 50 41 ved) cerr << "PA
0e40: 53 53 45 44 22 20 3c 3c 20 65 6e 64 6c 3b 20 65 SSED" << endl; e
0e50: 6c 73 65 20 7b 20 63 65 72 72 20 3c 3c 20 22 46 lse { cerr << "F
0e60: 41 49 4c 45 44 22 20 3c 3c 20 65 6e 64 6c 3b 20 AILED" << endl;
0e70: 63 65 72 72 20 3c 3c 20 22 5c 74 45 78 70 65 63 cerr << "\tExpec
0e80: 74 65 64 3a 20 5c 22 22 20 3c 3c 20 45 78 70 65 ted: \"" << Expe
0e90: 63 74 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 cted << '\"' <<
0ea0: 65 6e 64 6c 3b 20 63 65 72 72 20 3c 3c 20 22 5c endl; cerr << "\
0eb0: 74 52 65 63 65 69 76 65 64 3a 20 5c 22 22 20 3c tReceived: \"" <
0ec0: 3c 20 52 65 63 65 69 76 65 64 20 3c 3c 20 27 5c < Received << '\
0ed0: 22 27 20 3c 3c 20 65 6e 64 6c 3b 20 7d 20 7d 0d "' << endl; } }.
0ee0: 0a 09 76 6f 69 64 20 74 65 73 74 5f 63 61 73 65 ..void test_case
0ef0: 5f 30 28 29 20 7b 20 69 6e 74 20 41 72 72 30 5b _0() { int Arr0[
0f00: 5d 20 3d 20 7b 31 2c 32 2c 33 2c 34 2c 30 7d 3b ] = {1,2,3,4,0};
0f10: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 41 72 vector <int> Ar
0f20: 67 30 28 41 72 72 30 2c 20 41 72 72 30 20 2b 20 g0(Arr0, Arr0 +
0f30: 28 73 69 7a 65 6f 66 28 41 72 72 30 29 20 2f 20 (sizeof(Arr0) /
0f40: 73 69 7a 65 6f 66 28 41 72 72 30 5b 30 5d 29 29 sizeof(Arr0[0]))
0f50: 29 3b 20 69 6e 74 20 41 72 72 31 5b 5d 20 3d 20 ); int Arr1[] =
0f60: 7b 31 2c 31 2c 31 2c 31 2c 31 7d 3b 20 76 65 63 {1,1,1,1,1}; vec
0f70: 74 6f 72 20 3c 69 6e 74 3e 20 41 72 67 31 28 41 tor <int> Arg1(A
0f80: 72 72 31 2c 20 41 72 72 31 20 2b 20 28 73 69 7a rr1, Arr1 + (siz
0f90: 65 6f 66 28 41 72 72 31 29 20 2f 20 73 69 7a 65 eof(Arr1) / size
0fa0: 6f 66 28 41 72 72 31 5b 30 5d 29 29 29 3b 20 76 of(Arr1[0]))); v
0fb0: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 41 72 67 32 ector <int> Arg2
0fc0: 3b 20 69 6e 74 20 41 72 67 33 20 3d 20 31 3b 20 ; int Arg3 = 1;
0fd0: 69 6e 74 20 41 72 67 34 20 3d 20 32 3b 20 76 65 int Arg4 = 2; ve
0fe0: 72 69 66 79 5f 63 61 73 65 28 30 2c 20 41 72 67 rify_case(0, Arg
0ff0: 34 2c 20 62 75 69 6c 64 43 61 73 74 6c 65 73 28 4, buildCastles(
1000: 41 72 67 30 2c 20 41 72 67 31 2c 20 41 72 67 32 Arg0, Arg1, Arg2
1010: 2c 20 41 72 67 33 29 29 3b 20 7d 0d 0a 09 76 6f , Arg3)); }...vo
1020: 69 64 20 74 65 73 74 5f 63 61 73 65 5f 31 28 29 id test_case_1()
1030: 20 7b 20 69 6e 74 20 41 72 72 30 5b 5d 20 3d 20 { int Arr0[] =
1040: 7b 31 2c 32 2c 30 7d 3b 20 76 65 63 74 6f 72 20 {1,2,0}; vector
1050: 3c 69 6e 74 3e 20 41 72 67 30 28 41 72 72 30 2c <int> Arg0(Arr0,
1060: 20 41 72 72 30 20 2b 20 28 73 69 7a 65 6f 66 28 Arr0 + (sizeof(
1070: 41 72 72 30 29 20 2f 20 73 69 7a 65 6f 66 28 41 Arr0) / sizeof(A
1080: 72 72 30 5b 30 5d 29 29 29 3b 20 69 6e 74 20 41 rr0[0]))); int A
1090: 72 72 31 5b 5d 20 3d 20 7b 31 2c 32 2c 33 7d 3b rr1[] = {1,2,3};
10a0: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 41 72 vector <int> Ar
10b0: 67 31 28 41 72 72 31 2c 20 41 72 72 31 20 2b 20 g1(Arr1, Arr1 +
10c0: 28 73 69 7a 65 6f 66 28 41 72 72 31 29 20 2f 20 (sizeof(Arr1) /
10d0: 73 69 7a 65 6f 66 28 41 72 72 31 5b 30 5d 29 29 sizeof(Arr1[0]))
10e0: 29 3b 20 69 6e 74 20 41 72 72 32 5b 5d 20 3d 20 ); int Arr2[] =
10f0: 7b 32 7d 3b 20 76 65 63 74 6f 72 20 3c 69 6e 74 {2}; vector <int
1100: 3e 20 41 72 67 32 28 41 72 72 32 2c 20 41 72 72 > Arg2(Arr2, Arr
1110: 32 20 2b 20 28 73 69 7a 65 6f 66 28 41 72 72 32 2 + (sizeof(Arr2
1120: 29 20 2f 20 73 69 7a 65 6f 66 28 41 72 72 32 5b ) / sizeof(Arr2[
1130: 30 5d 29 29 29 3b 20 69 6e 74 20 41 72 67 33 20 0]))); int Arg3
1140: 3d 20 31 3b 20 69 6e 74 20 41 72 67 34 20 3d 20 = 1; int Arg4 =
1150: 31 3b 20 76 65 72 69 66 79 5f 63 61 73 65 28 31 1; verify_case(1
1160: 2c 20 41 72 67 34 2c 20 62 75 69 6c 64 43 61 73 , Arg4, buildCas
1170: 74 6c 65 73 28 41 72 67 30 2c 20 41 72 67 31 2c tles(Arg0, Arg1,
1180: 20 41 72 67 32 2c 20 41 72 67 33 29 29 3b 20 7d Arg2, Arg3)); }
1190: 0d 0a 09 76 6f 69 64 20 74 65 73 74 5f 63 61 73 ...void test_cas
11a0: 65 5f 32 28 29 20 7b 20 69 6e 74 20 41 72 72 30 e_2() { int Arr0
11b0: 5b 5d 20 3d 20 7b 30 2c 31 7d 3b 20 76 65 63 74 [] = {0,1}; vect
11c0: 6f 72 20 3c 69 6e 74 3e 20 41 72 67 30 28 41 72 or <int> Arg0(Ar
11d0: 72 30 2c 20 41 72 72 30 20 2b 20 28 73 69 7a 65 r0, Arr0 + (size
11e0: 6f 66 28 41 72 72 30 29 20 2f 20 73 69 7a 65 6f of(Arr0) / sizeo
11f0: 66 28 41 72 72 30 5b 30 5d 29 29 29 3b 20 69 6e f(Arr0[0]))); in
1200: 74 20 41 72 72 31 5b 5d 20 3d 20 7b 31 2c 31 7d t Arr1[] = {1,1}
1210: 3b 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 41 ; vector <int> A
1220: 72 67 31 28 41 72 72 31 2c 20 41 72 72 31 20 2b rg1(Arr1, Arr1 +
1230: 20 28 73 69 7a 65 6f 66 28 41 72 72 31 29 20 2f (sizeof(Arr1) /
1240: 20 73 69 7a 65 6f 66 28 41 72 72 31 5b 30 5d 29 sizeof(Arr1[0])
1250: 29 29 3b 20 69 6e 74 20 41 72 72 32 5b 5d 20 3d )); int Arr2[] =
1260: 20 7b 31 7d 3b 20 76 65 63 74 6f 72 20 3c 69 6e {1}; vector <in
1270: 74 3e 20 41 72 67 32 28 41 72 72 32 2c 20 41 72 t> Arg2(Arr2, Ar
1280: 72 32 20 2b 20 28 73 69 7a 65 6f 66 28 41 72 72 r2 + (sizeof(Arr
1290: 32 29 20 2f 20 73 69 7a 65 6f 66 28 41 72 72 32 2) / sizeof(Arr2
12a0: 5b 30 5d 29 29 29 3b 20 69 6e 74 20 41 72 67 33 [0]))); int Arg3
12b0: 20 3d 20 31 3b 20 69 6e 74 20 41 72 67 34 20 3d = 1; int Arg4 =
12c0: 20 30 3b 20 76 65 72 69 66 79 5f 63 61 73 65 28 0; verify_case(
12d0: 32 2c 20 41 72 67 34 2c 20 62 75 69 6c 64 43 61 2, Arg4, buildCa
12e0: 73 74 6c 65 73 28 41 72 67 30 2c 20 41 72 67 31 stles(Arg0, Arg1
12f0: 2c 20 41 72 67 32 2c 20 41 72 67 33 29 29 3b 20 , Arg2, Arg3));
1300: 7d 0d 0a 09 76 6f 69 64 20 74 65 73 74 5f 63 61 }...void test_ca
1310: 73 65 5f 33 28 29 20 7b 20 69 6e 74 20 41 72 72 se_3() { int Arr
1320: 30 5b 5d 20 3d 20 7b 30 2c 32 2c 30 2c 30 2c 32 0[] = {0,2,0,0,2
1330: 2c 32 2c 38 2c 33 2c 38 2c 37 7d 3b 20 76 65 63 ,2,8,3,8,7}; vec
1340: 74 6f 72 20 3c 69 6e 74 3e 20 41 72 67 30 28 41 tor <int> Arg0(A
1350: 72 72 30 2c 20 41 72 72 30 20 2b 20 28 73 69 7a rr0, Arr0 + (siz
1360: 65 6f 66 28 41 72 72 30 29 20 2f 20 73 69 7a 65 eof(Arr0) / size
1370: 6f 66 28 41 72 72 30 5b 30 5d 29 29 29 3b 20 69 of(Arr0[0]))); i
1380: 6e 74 20 41 72 72 31 5b 5d 20 3d 20 7b 31 30 2c nt Arr1[] = {10,
1390: 39 2c 31 2c 38 2c 31 2c 33 2c 37 2c 32 2c 38 2c 9,1,8,1,3,7,2,8,
13a0: 31 7d 3b 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 1}; vector <int>
13b0: 20 41 72 67 31 28 41 72 72 31 2c 20 41 72 72 31 Arg1(Arr1, Arr1
13c0: 20 2b 20 28 73 69 7a 65 6f 66 28 41 72 72 31 29 + (sizeof(Arr1)
13d0: 20 2f 20 73 69 7a 65 6f 66 28 41 72 72 31 5b 30 / sizeof(Arr1[0
13e0: 5d 29 29 29 3b 20 69 6e 74 20 41 72 72 32 5b 5d ]))); int Arr2[]
13f0: 20 3d 20 7b 33 2c 34 2c 36 7d 3b 20 76 65 63 74 = {3,4,6}; vect
1400: 6f 72 20 3c 69 6e 74 3e 20 41 72 67 32 28 41 72 or <int> Arg2(Ar
1410: 72 32 2c 20 41 72 72 32 20 2b 20 28 73 69 7a 65 r2, Arr2 + (size
1420: 6f 66 28 41 72 72 32 29 20 2f 20 73 69 7a 65 6f of(Arr2) / sizeo
1430: 66 28 41 72 72 32 5b 30 5d 29 29 29 3b 20 69 6e f(Arr2[0]))); in
1440: 74 20 41 72 67 33 20 3d 20 33 3b 20 69 6e 74 20 t Arg3 = 3; int
1450: 41 72 67 34 20 3d 20 33 3b 20 76 65 72 69 66 79 Arg4 = 3; verify
1460: 5f 63 61 73 65 28 33 2c 20 41 72 67 34 2c 20 62 _case(3, Arg4, b
1470: 75 69 6c 64 43 61 73 74 6c 65 73 28 41 72 67 30 uildCastles(Arg0
1480: 2c 20 41 72 67 31 2c 20 41 72 67 32 2c 20 41 72 , Arg1, Arg2, Ar
1490: 67 33 29 29 3b 20 7d 0d 0a 09 76 6f 69 64 20 74 g3)); }...void t
14a0: 65 73 74 5f 63 61 73 65 5f 34 28 29 20 7b 20 69 est_case_4() { i
14b0: 6e 74 20 41 72 72 30 5b 5d 20 3d 20 7b 31 2c 20 nt Arr0[] = {1,
14c0: 30 7d 3b 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 0}; vector <int>
14d0: 20 41 72 67 30 28 41 72 72 30 2c 20 41 72 72 30 Arg0(Arr0, Arr0
14e0: 20 2b 20 28 73 69 7a 65 6f 66 28 41 72 72 30 29 + (sizeof(Arr0)
14f0: 20 2f 20 73 69 7a 65 6f 66 28 41 72 72 30 5b 30 / sizeof(Arr0[0
1500: 5d 29 29 29 3b 20 69 6e 74 20 41 72 72 31 5b 5d ]))); int Arr1[]
1510: 20 3d 20 7b 35 2c 20 31 30 7d 3b 20 76 65 63 74 = {5, 10}; vect
1520: 6f 72 20 3c 69 6e 74 3e 20 41 72 67 31 28 41 72 or <int> Arg1(Ar
1530: 72 31 2c 20 41 72 72 31 20 2b 20 28 73 69 7a 65 r1, Arr1 + (size
1540: 6f 66 28 41 72 72 31 29 20 2f 20 73 69 7a 65 6f of(Arr1) / sizeo
1550: 66 28 41 72 72 31 5b 30 5d 29 29 29 3b 20 76 65 f(Arr1[0]))); ve
1560: 63 74 6f 72 20 3c 69 6e 74 3e 20 41 72 67 32 3b ctor <int> Arg2;
1570: 20 69 6e 74 20 41 72 67 33 20 3d 20 31 3b 20 69 int Arg3 = 1; i
1580: 6e 74 20 41 72 67 34 20 3d 20 35 3b 20 76 65 72 nt Arg4 = 5; ver
1590: 69 66 79 5f 63 61 73 65 28 34 2c 20 41 72 67 34 ify_case(4, Arg4
15a0: 2c 20 62 75 69 6c 64 43 61 73 74 6c 65 73 28 41 , buildCastles(A
15b0: 72 67 30 2c 20 41 72 67 31 2c 20 41 72 67 32 2c rg0, Arg1, Arg2,
15c0: 20 41 72 67 33 29 29 3b 20 7d 0d 0a 0d 0a 2f 2f Arg3)); }....//
15d0: 20 45 4e 44 20 43 55 54 20 48 45 52 45 0d 0a 7d END CUT HERE..}
15e0: 3b 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 55 54 20 ;..// BEGIN CUT
15f0: 48 45 52 45 20 0d 0a 69 6e 74 20 6d 61 69 6e 28 HERE ..int main(
1600: 29 20 7b 20 42 79 74 65 4c 61 6e 64 28 29 2e 72 ) { ByteLand().r
1610: 75 6e 5f 74 65 73 74 28 2d 31 29 3b 20 7d 0d 0a un_test(-1); }..
1620: 2f 2f 20 45 4e 44 20 43 55 54 20 48 45 52 45 0d // END CUT HERE.
1630: 0a .