69a17ebf8a 2021-07-08 kinaba: #include <iostream> 69a17ebf8a 2021-07-08 kinaba: #include <sstream> 69a17ebf8a 2021-07-08 kinaba: #include <iomanip> 69a17ebf8a 2021-07-08 kinaba: #include <vector> 69a17ebf8a 2021-07-08 kinaba: #include <string> 69a17ebf8a 2021-07-08 kinaba: #include <map> 69a17ebf8a 2021-07-08 kinaba: #include <set> 69a17ebf8a 2021-07-08 kinaba: #include <algorithm> 69a17ebf8a 2021-07-08 kinaba: #include <numeric> 69a17ebf8a 2021-07-08 kinaba: #include <iterator> 69a17ebf8a 2021-07-08 kinaba: #include <functional> 69a17ebf8a 2021-07-08 kinaba: #include <complex> 69a17ebf8a 2021-07-08 kinaba: #include <queue> 69a17ebf8a 2021-07-08 kinaba: #include <stack> 69a17ebf8a 2021-07-08 kinaba: #include <cmath> 69a17ebf8a 2021-07-08 kinaba: #include <cassert> 69a17ebf8a 2021-07-08 kinaba: #include <tuple> 69a17ebf8a 2021-07-08 kinaba: using namespace std; 69a17ebf8a 2021-07-08 kinaba: typedef long long LL; 69a17ebf8a 2021-07-08 kinaba: typedef complex<double> CMP; 69a17ebf8a 2021-07-08 kinaba: 69a17ebf8a 2021-07-08 kinaba: class TellBagsApart { public: 69a17ebf8a 2021-07-08 kinaba: string whichBagIsSmaller(vector <int> records) 69a17ebf8a 2021-07-08 kinaba: { 69a17ebf8a 2021-07-08 kinaba: srand(time(0)); 69a17ebf8a 2021-07-08 kinaba: string ans; 69a17ebf8a 2021-07-08 kinaba: for (int i = 0; i < records.size(); i += 8) 69a17ebf8a 2021-07-08 kinaba: ans += char('0' + solve(vector<int>(records.begin() + i, records.begin() + i + 8))); 69a17ebf8a 2021-07-08 kinaba: return ans; 69a17ebf8a 2021-07-08 kinaba: } 69a17ebf8a 2021-07-08 kinaba: 69a17ebf8a 2021-07-08 kinaba: int solve(vector<int> r) { 69a17ebf8a 2021-07-08 kinaba: // same = 3/7, diff = 4/7 69a17ebf8a 2021-07-08 kinaba: // same = 19/39, diff = 20/39 69a17ebf8a 2021-07-08 kinaba: int a1 = r[0] + r[1] + r[2] + r[3]; 69a17ebf8a 2021-07-08 kinaba: int s1 = r[0] + r[3]; 69a17ebf8a 2021-07-08 kinaba: int d1 = a1 - s1; 69a17ebf8a 2021-07-08 kinaba: int a2 = r[4] + r[5] + r[6] + r[7]; 69a17ebf8a 2021-07-08 kinaba: int s2 = r[4] + r[7]; 69a17ebf8a 2021-07-08 kinaba: int d2 = a2 - s2; 69a17ebf8a 2021-07-08 kinaba: int lhs, rhs; 69a17ebf8a 2021-07-08 kinaba: if (a1 == 0) { 69a17ebf8a 2021-07-08 kinaba: // s2/a2 closer to 19/39 ? 1 : 2 69a17ebf8a 2021-07-08 kinaba: // 125/273 < s2/a2 69a17ebf8a 2021-07-08 kinaba: lhs = 125 * a2; 69a17ebf8a 2021-07-08 kinaba: rhs = s2 * 273; 69a17ebf8a 2021-07-08 kinaba: } 69a17ebf8a 2021-07-08 kinaba: else if (a2 == 0) { 69a17ebf8a 2021-07-08 kinaba: // s1/a1 closer to 3/7 ? 1 : 2 69a17ebf8a 2021-07-08 kinaba: // s1/a1 < 125/273 69a17ebf8a 2021-07-08 kinaba: lhs = s1 * 273; 69a17ebf8a 2021-07-08 kinaba: rhs = 125 * a1; 69a17ebf8a 2021-07-08 kinaba: } 69a17ebf8a 2021-07-08 kinaba: else { 69a17ebf8a 2021-07-08 kinaba: // s1/a1 < s2/a2 ? 1 : 2 69a17ebf8a 2021-07-08 kinaba: lhs = s1 * a2; 69a17ebf8a 2021-07-08 kinaba: rhs = s2 * a1; 69a17ebf8a 2021-07-08 kinaba: } 69a17ebf8a 2021-07-08 kinaba: 69a17ebf8a 2021-07-08 kinaba: if (lhs == rhs) { 69a17ebf8a 2021-07-08 kinaba: return (rand() >> 8) & 1 ? 1 : 2; 69a17ebf8a 2021-07-08 kinaba: } 69a17ebf8a 2021-07-08 kinaba: else { 69a17ebf8a 2021-07-08 kinaba: return lhs < rhs ? 1 : 2; 69a17ebf8a 2021-07-08 kinaba: } 69a17ebf8a 2021-07-08 kinaba: } 69a17ebf8a 2021-07-08 kinaba: }; 69a17ebf8a 2021-07-08 kinaba: 69a17ebf8a 2021-07-08 kinaba: // BEGIN CUT HERE 69a17ebf8a 2021-07-08 kinaba: #include <ctime> 69a17ebf8a 2021-07-08 kinaba: double start_time; string timer() 69a17ebf8a 2021-07-08 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 69a17ebf8a 2021-07-08 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 69a17ebf8a 2021-07-08 kinaba: { os << "{ "; 69a17ebf8a 2021-07-08 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 69a17ebf8a 2021-07-08 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 69a17ebf8a 2021-07-08 kinaba: void verify_case(const string& Expected, const string& Received) { 69a17ebf8a 2021-07-08 kinaba: bool ok = (Expected == Received); 69a17ebf8a 2021-07-08 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 69a17ebf8a 2021-07-08 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 69a17ebf8a 2021-07-08 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 69a17ebf8a 2021-07-08 kinaba: #define END verify_case(_, TellBagsApart().whichBagIsSmaller(records));} 69a17ebf8a 2021-07-08 kinaba: int main(){ 69a17ebf8a 2021-07-08 kinaba: 69a17ebf8a 2021-07-08 kinaba: CASE(0) 69a17ebf8a 2021-07-08 kinaba: int records_[] = {262, 371, 340, 277, 303, 304, 333, 310, 69a17ebf8a 2021-07-08 kinaba: 296, 326, 370, 275, 312, 329, 284, 308, 69a17ebf8a 2021-07-08 kinaba: 265, 402, 372, 279, 279, 317, 307, 279, 69a17ebf8a 2021-07-08 kinaba: 112, 160, 121, 102, 497, 497, 505, 506}; 69a17ebf8a 2021-07-08 kinaba: vector <int> records(records_, records_+sizeof(records_)/sizeof(*records_)); 69a17ebf8a 2021-07-08 kinaba: string _ = "1111"; 69a17ebf8a 2021-07-08 kinaba: END 69a17ebf8a 2021-07-08 kinaba: CASE(1) 69a17ebf8a 2021-07-08 kinaba: int records_[] = {401, 405, 345, 358, 203, 295, 284, 209, 69a17ebf8a 2021-07-08 kinaba: 348, 380, 396, 361, 221, 274, 307, 213, 69a17ebf8a 2021-07-08 kinaba: 361, 347, 410, 347, 246, 287, 298, 204, 69a17ebf8a 2021-07-08 kinaba: 301, 389, 412, 304, 253, 289, 280, 272, 69a17ebf8a 2021-07-08 kinaba: 303, 450, 388, 290, 270, 286, 246, 267, 69a17ebf8a 2021-07-08 kinaba: 328, 354, 326, 362, 254, 305, 309, 262, 69a17ebf8a 2021-07-08 kinaba: 290, 362, 391, 296, 285, 282, 313, 281, 69a17ebf8a 2021-07-08 kinaba: 338, 335, 345, 335, 220, 338, 335, 254, 69a17ebf8a 2021-07-08 kinaba: 309, 356, 348, 323, 239, 344, 343, 238, 69a17ebf8a 2021-07-08 kinaba: 264, 368, 365, 258, 301, 312, 328, 304, 69a17ebf8a 2021-07-08 kinaba: 256, 368, 343, 295, 296, 323, 319, 300, 69a17ebf8a 2021-07-08 kinaba: 275, 318, 383, 258, 320, 340, 306, 300, 69a17ebf8a 2021-07-08 kinaba: 275, 301, 323, 309, 273, 372, 366, 281, 69a17ebf8a 2021-07-08 kinaba: 263, 331, 290, 309, 277, 358, 395, 277, 69a17ebf8a 2021-07-08 kinaba: 261, 310, 291, 259, 301, 407, 379, 292, 69a17ebf8a 2021-07-08 kinaba: 256, 318, 297, 257, 325, 358, 366, 323, 69a17ebf8a 2021-07-08 kinaba: 284, 287, 274, 286, 294, 406, 358, 311, 69a17ebf8a 2021-07-08 kinaba: 266, 271, 282, 256, 282, 395, 429, 319, 69a17ebf8a 2021-07-08 kinaba: 270, 274, 278, 268, 308, 396, 404, 302, 69a17ebf8a 2021-07-08 kinaba: 203, 283, 299, 229, 368, 401, 377, 340}; 69a17ebf8a 2021-07-08 kinaba: vector <int> records(records_, records_+sizeof(records_)/sizeof(*records_)); 69a17ebf8a 2021-07-08 kinaba: string _ = "22211212211122212221"; 69a17ebf8a 2021-07-08 kinaba: END 69a17ebf8a 2021-07-08 kinaba: /* 69a17ebf8a 2021-07-08 kinaba: CASE(2) 69a17ebf8a 2021-07-08 kinaba: int records_[] = ; 69a17ebf8a 2021-07-08 kinaba: vector <int> records(records_, records_+sizeof(records_)/sizeof(*records_)); 69a17ebf8a 2021-07-08 kinaba: string _ = ; 69a17ebf8a 2021-07-08 kinaba: END 69a17ebf8a 2021-07-08 kinaba: CASE(3) 69a17ebf8a 2021-07-08 kinaba: int records_[] = ; 69a17ebf8a 2021-07-08 kinaba: vector <int> records(records_, records_+sizeof(records_)/sizeof(*records_)); 69a17ebf8a 2021-07-08 kinaba: string _ = ; 69a17ebf8a 2021-07-08 kinaba: END 69a17ebf8a 2021-07-08 kinaba: */ 69a17ebf8a 2021-07-08 kinaba: } 69a17ebf8a 2021-07-08 kinaba: // END CUT HERE