Artifact 8b7e23cf8b869fd67d51dea1cf69665558207ca4:
0000: 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d //--------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0040: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
0050: 2f 2f 20 3e 3e 43 6f 64 65 20 54 65 6d 70 6c 61 // >>Code Templa
0060: 74 65 3c 3c 20 28 66 6f 72 20 56 69 73 75 61 6c te<< (for Visual
0070: 20 43 2b 2b 29 0a 0a 23 69 6e 63 6c 75 64 65 20 C++)..#include
0080: 3c 69 6f 73 74 72 65 61 6d 3e 0a 23 69 6e 63 6c <iostream>.#incl
0090: 75 64 65 20 3c 73 73 74 72 65 61 6d 3e 0a 23 69 ude <sstream>.#i
00a0: 6e 63 6c 75 64 65 20 3c 69 6f 6d 61 6e 69 70 3e nclude <iomanip>
00b0: 0a 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 6e .#include <strin
00c0: 67 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 76 65 63 g>.#include <vec
00d0: 74 6f 72 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 73 tor>.#include <s
00e0: 65 74 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 6d 61 et>.#include <ma
00f0: 70 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 61 6c 67 p>.#include <alg
0100: 6f 72 69 74 68 6d 3e 0a 23 69 6e 63 6c 75 64 65 orithm>.#include
0110: 20 3c 6e 75 6d 65 72 69 63 3e 0a 23 69 6e 63 6c <numeric>.#incl
0120: 75 64 65 20 3c 69 74 65 72 61 74 6f 72 3e 0a 23 ude <iterator>.#
0130: 69 6e 63 6c 75 64 65 20 3c 63 6f 6d 70 6c 65 78 include <complex
0140: 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 66 75 6e 63 >.#include <func
0150: 74 69 6f 6e 61 6c 3e 0a 23 69 6e 63 6c 75 64 65 tional>.#include
0160: 20 3c 71 75 65 75 65 3e 0a 23 69 6e 63 6c 75 64 <queue>.#includ
0170: 65 20 3c 73 74 61 63 6b 3e 0a 23 69 6e 63 6c 75 e <stack>.#inclu
0180: 64 65 20 3c 63 6d 61 74 68 3e 0a 23 69 6e 63 6c de <cmath>.#incl
0190: 75 64 65 20 3c 63 61 73 73 65 72 74 3e 0a 23 69 ude <cassert>.#i
01a0: 6e 63 6c 75 64 65 20 3c 63 73 74 72 69 6e 67 3e nclude <cstring>
01b0: 0a 23 64 65 66 69 6e 65 20 20 63 6f 75 74 20 6f .#define cout o
01c0: 73 0a 75 73 69 6e 67 20 6e 61 6d 65 73 70 61 63 s.using namespac
01d0: 65 20 73 74 64 3b 0a 74 79 70 65 64 65 66 20 6c e std;.typedef l
01e0: 6f 6e 67 20 6c 6f 6e 67 20 4c 4c 3b 0a 74 79 70 ong long LL;.typ
01f0: 65 64 65 66 20 63 6f 6d 70 6c 65 78 3c 64 6f 75 edef complex<dou
0200: 62 6c 65 3e 20 43 4d 50 3b 0a 76 6f 69 64 20 45 ble> CMP;.void E
0210: 4e 44 5f 4f 46 5f 49 4e 50 55 54 5f 46 4f 52 5f ND_OF_INPUT_FOR_
0220: 54 48 49 53 5f 54 45 53 54 5f 43 41 53 45 28 29 THIS_TEST_CASE()
0230: 3b 20 2f 2f 20 73 74 75 62 20 66 6f 72 20 6d 75 ; // stub for mu
0240: 6c 74 69 2d 74 68 72 65 61 64 69 6e 67 0a 0a 2f lti-threading../
0250: 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d /---------------
0260: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0270: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0280: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0290: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 2f --------------./
02a0: 2f 20 3e 3e 4d 61 69 6e 3c 3c 0a 0a 76 6f 69 64 / >>Main<<..void
02b0: 20 63 61 73 65 5f 6d 61 69 6e 28 20 6f 73 74 72 case_main( ostr
02c0: 65 61 6d 26 20 6f 73 20 29 0a 7b 0a 09 45 4e 44 eam& os ).{..END
02d0: 5f 4f 46 5f 49 4e 50 55 54 5f 46 4f 52 5f 54 48 _OF_INPUT_FOR_TH
02e0: 49 53 5f 54 45 53 54 5f 43 41 53 45 28 29 3b 0a IS_TEST_CASE();.
02f0: 7d 0a 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d }..//-----------
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 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0340: 2d 2d 0a 2f 2f 20 3e 3e 43 6f 64 65 20 54 65 6d --.// >>Code Tem
0350: 70 6c 61 74 65 3c 3c 20 28 4d 75 6c 74 69 2d 54 plate<< (Multi-T
0360: 68 72 65 61 64 20 53 6f 6c 76 65 72 29 0a 0a 23 hread Solver)..#
0370: 69 66 20 31 0a 23 75 6e 64 65 66 20 63 6f 75 74 if 1.#undef cout
0380: 0a 23 69 6e 63 6c 75 64 65 20 3c 77 69 6e 64 6f .#include <windo
0390: 77 73 2e 68 3e 0a 23 69 6e 63 6c 75 64 65 20 3c ws.h>.#include <
03a0: 70 72 6f 63 65 73 73 2e 68 3e 0a 0a 73 74 61 74 process.h>..stat
03b0: 69 63 20 63 6f 6e 73 74 20 69 6e 74 20 54 48 52 ic const int THR
03c0: 45 41 44 5f 4e 55 4d 20 3d 20 32 3b 0a 76 6f 6c EAD_NUM = 2;.vol
03d0: 61 74 69 6c 65 20 69 6e 74 20 20 20 20 20 67 5f atile int g_
03e0: 69 64 3b 0a 69 6e 74 20 20 20 20 20 20 20 20 20 id;.int
03f0: 20 20 20 20 20 67 5f 6e 43 61 73 65 3b 0a 43 52 g_nCase;.CR
0400: 49 54 49 43 41 4c 5f 53 45 43 54 49 4f 4e 20 67 ITICAL_SECTION g
0410: 5f 63 73 3b 0a 76 65 63 74 6f 72 3c 73 74 72 69 _cs;.vector<stri
0420: 6e 67 3e 20 20 20 67 5f 6f 75 74 70 75 74 3b 0a ng> g_output;.
0430: 0a 75 6e 73 69 67 6e 65 64 20 5f 5f 73 74 64 63 .unsigned __stdc
0440: 61 6c 6c 20 74 68 72 65 61 64 5f 6d 61 69 6e 28 all thread_main(
0450: 20 76 6f 69 64 2a 20 74 5f 69 64 20 29 20 7b 0a void* t_id ) {.
0460: 09 66 6f 72 28 3b 3b 29 20 7b 0a 09 09 45 6e 74 .for(;;) {...Ent
0470: 65 72 43 72 69 74 69 63 61 6c 53 65 63 74 69 6f erCriticalSectio
0480: 6e 28 26 67 5f 63 73 29 3b 0a 09 09 63 6f 6e 73 n(&g_cs);...cons
0490: 74 20 69 6e 74 20 69 64 20 3d 20 2b 2b 67 5f 69 t int id = ++g_i
04a0: 64 3b 0a 09 09 69 66 28 69 64 3e 67 5f 6e 43 61 d;...if(id>g_nCa
04b0: 73 65 29 20 7b 20 4c 65 61 76 65 43 72 69 74 69 se) { LeaveCriti
04c0: 63 61 6c 53 65 63 74 69 6f 6e 28 26 67 5f 63 73 calSection(&g_cs
04d0: 29 3b 20 62 72 65 61 6b 3b 20 7d 0a 09 09 63 65 ); break; }...ce
04e0: 72 72 20 3c 3c 20 73 65 74 77 28 34 29 20 3c 3c rr << setw(4) <<
04f0: 20 69 64 20 3c 3c 20 22 20 40 20 22 20 3c 3c 20 id << " @ " <<
0500: 28 69 6e 74 29 74 5f 69 64 20 3c 3c 20 22 20 73 (int)t_id << " s
0510: 74 61 72 74 22 20 3c 3c 20 65 6e 64 6c 3b 0a 0a tart" << endl;..
0520: 09 09 6f 73 74 72 69 6e 67 73 74 72 65 61 6d 20 ..ostringstream
0530: 73 73 3b 0a 09 09 73 73 20 3c 3c 20 22 43 61 73 ss;...ss << "Cas
0540: 65 20 23 22 20 3c 3c 20 69 64 20 3c 3c 20 22 3a e #" << id << ":
0550: 20 22 3b 0a 09 09 63 61 73 65 5f 6d 61 69 6e 28 ";...case_main(
0560: 20 73 73 20 29 3b 0a 0a 09 09 45 6e 74 65 72 43 ss );....EnterC
0570: 72 69 74 69 63 61 6c 53 65 63 74 69 6f 6e 28 26 riticalSection(&
0580: 67 5f 63 73 29 3b 0a 09 09 69 66 28 67 5f 6f 75 g_cs);...if(g_ou
0590: 74 70 75 74 2e 73 69 7a 65 28 29 3c 69 64 29 20 tput.size()<id)
05a0: 67 5f 6f 75 74 70 75 74 2e 72 65 73 69 7a 65 28 g_output.resize(
05b0: 69 64 29 3b 0a 09 09 67 5f 6f 75 74 70 75 74 5b id);...g_output[
05c0: 69 64 2d 31 5d 20 3d 20 73 73 2e 73 74 72 28 29 id-1] = ss.str()
05d0: 3b 0a 09 09 63 65 72 72 20 3c 3c 20 73 65 74 77 ;...cerr << setw
05e0: 28 34 29 20 3c 3c 20 69 64 20 3c 3c 20 22 20 40 (4) << id << " @
05f0: 20 22 20 3c 3c 20 28 69 6e 74 29 74 5f 69 64 20 " << (int)t_id
0600: 3c 3c 20 22 20 65 6e 64 22 20 3c 3c 20 65 6e 64 << " end" << end
0610: 6c 3b 0a 09 09 4c 65 61 76 65 43 72 69 74 69 63 l;...LeaveCritic
0620: 61 6c 53 65 63 74 69 6f 6e 28 26 67 5f 63 73 29 alSection(&g_cs)
0630: 3b 0a 09 7d 0a 09 72 65 74 75 72 6e 20 30 3b 0a ;..}..return 0;.
0640: 7d 0a 0a 76 6f 69 64 20 45 4e 44 5f 4f 46 5f 49 }..void END_OF_I
0650: 4e 50 55 54 5f 46 4f 52 5f 54 48 49 53 5f 54 45 NPUT_FOR_THIS_TE
0660: 53 54 5f 43 41 53 45 28 29 20 7b 20 4c 65 61 76 ST_CASE() { Leav
0670: 65 43 72 69 74 69 63 61 6c 53 65 63 74 69 6f 6e eCriticalSection
0680: 28 26 67 5f 63 73 29 3b 20 7d 0a 0a 69 6e 74 20 (&g_cs); }..int
0690: 6d 61 69 6e 28 29 20 7b 0a 09 63 69 6e 20 3e 3e main() {..cin >>
06a0: 20 67 5f 6e 43 61 73 65 3b 0a 09 73 74 72 69 6e g_nCase;..strin
06b0: 67 20 64 75 6d 6d 79 3b 20 67 65 74 6c 69 6e 65 g dummy; getline
06c0: 28 63 69 6e 2c 20 64 75 6d 6d 79 29 3b 0a 0a 09 (cin, dummy);...
06d0: 49 6e 69 74 69 61 6c 69 7a 65 43 72 69 74 69 63 InitializeCritic
06e0: 61 6c 53 65 63 74 69 6f 6e 28 26 67 5f 63 73 29 alSection(&g_cs)
06f0: 3b 0a 09 76 65 63 74 6f 72 3c 48 41 4e 44 4c 45 ;..vector<HANDLE
0700: 3e 20 74 68 72 65 61 64 3b 0a 09 66 6f 72 28 69 > thread;..for(i
0710: 6e 74 20 69 3d 30 3b 20 69 3c 54 48 52 45 41 44 nt i=0; i<THREAD
0720: 5f 4e 55 4d 3b 20 2b 2b 69 29 0a 09 09 74 68 72 _NUM; ++i)...thr
0730: 65 61 64 2e 70 75 73 68 5f 62 61 63 6b 28 20 28 ead.push_back( (
0740: 48 41 4e 44 4c 45 29 5f 62 65 67 69 6e 74 68 72 HANDLE)_beginthr
0750: 65 61 64 65 78 28 30 2c 20 30 2c 20 26 74 68 72 eadex(0, 0, &thr
0760: 65 61 64 5f 6d 61 69 6e 2c 20 28 76 6f 69 64 2a ead_main, (void*
0770: 29 69 2c 20 30 2c 20 30 29 20 29 3b 0a 09 57 61 )i, 0, 0) );..Wa
0780: 69 74 46 6f 72 4d 75 6c 74 69 70 6c 65 4f 62 6a itForMultipleObj
0790: 65 63 74 73 28 20 74 68 72 65 61 64 2e 73 69 7a ects( thread.siz
07a0: 65 28 29 2c 20 26 74 68 72 65 61 64 5b 30 5d 2c e(), &thread[0],
07b0: 20 54 52 55 45 2c 20 49 4e 46 49 4e 49 54 45 20 TRUE, INFINITE
07c0: 29 3b 0a 09 44 65 6c 65 74 65 43 72 69 74 69 63 );..DeleteCritic
07d0: 61 6c 53 65 63 74 69 6f 6e 28 26 67 5f 63 73 29 alSection(&g_cs)
07e0: 3b 0a 0a 09 63 6f 70 79 28 20 67 5f 6f 75 74 70 ;...copy( g_outp
07f0: 75 74 2e 62 65 67 69 6e 28 29 2c 20 67 5f 6f 75 ut.begin(), g_ou
0800: 74 70 75 74 2e 65 6e 64 28 29 2c 20 6f 73 74 72 tput.end(), ostr
0810: 65 61 6d 5f 69 74 65 72 61 74 6f 72 3c 73 74 72 eam_iterator<str
0820: 69 6e 67 3e 28 63 6f 75 74 29 20 29 3b 0a 7d 0a ing>(cout) );.}.
0830: 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d .//-------------
0840: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0850: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0860: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0870: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0880: 0a 2f 2f 20 3e 3e 43 6f 64 65 20 54 65 6d 70 6c .// >>Code Templ
0890: 61 74 65 3c 3c 20 28 53 69 6e 67 6c 65 2d 54 68 ate<< (Single-Th
08a0: 72 65 61 64 20 53 6f 6c 76 65 72 29 0a 0a 23 65 read Solver)..#e
08b0: 6c 73 65 0a 23 75 6e 64 65 66 20 63 6f 75 74 0a lse.#undef cout.
08c0: 76 6f 69 64 20 45 4e 44 5f 4f 46 5f 49 4e 50 55 void END_OF_INPU
08d0: 54 5f 46 4f 52 5f 54 48 49 53 5f 54 45 53 54 5f T_FOR_THIS_TEST_
08e0: 43 41 53 45 28 29 20 7b 7d 0a 69 6e 74 20 6d 61 CASE() {}.int ma
08f0: 69 6e 28 29 20 7b 0a 09 69 6e 74 20 6e 43 61 73 in() {..int nCas
0900: 65 3b 20 63 69 6e 20 3e 3e 20 6e 43 61 73 65 3b e; cin >> nCase;
0910: 0a 09 73 74 72 69 6e 67 20 64 75 6d 6d 79 3b 20 ..string dummy;
0920: 67 65 74 6c 69 6e 65 28 63 69 6e 2c 20 64 75 6d getline(cin, dum
0930: 6d 79 29 3b 0a 0a 09 66 6f 72 28 69 6e 74 20 69 my);...for(int i
0940: 64 3d 31 3b 20 69 64 3c 3d 6e 43 61 73 65 3b 20 d=1; id<=nCase;
0950: 2b 2b 69 64 29 20 7b 0a 09 09 63 6f 75 74 20 3c ++id) {...cout <
0960: 3c 20 22 43 61 73 65 20 23 22 20 3c 3c 20 69 64 < "Case #" << id
0970: 20 3c 3c 20 22 3a 20 22 3b 0a 09 09 63 61 73 65 << ": ";...case
0980: 5f 6d 61 69 6e 28 20 63 6f 75 74 20 29 3b 0a 09 _main( cout );..
0990: 7d 0a 7d 0a 23 65 6e 64 69 66 0a }.}.#endif.