91eacbb0eb 2017-07-22 kinaba: #include <iostream> 91eacbb0eb 2017-07-22 kinaba: #include <sstream> 91eacbb0eb 2017-07-22 kinaba: #include <iomanip> 91eacbb0eb 2017-07-22 kinaba: #include <vector> 91eacbb0eb 2017-07-22 kinaba: #include <string> 91eacbb0eb 2017-07-22 kinaba: #include <map> 91eacbb0eb 2017-07-22 kinaba: #include <set> 91eacbb0eb 2017-07-22 kinaba: #include <algorithm> 91eacbb0eb 2017-07-22 kinaba: #include <numeric> 91eacbb0eb 2017-07-22 kinaba: #include <iterator> 91eacbb0eb 2017-07-22 kinaba: #include <functional> 91eacbb0eb 2017-07-22 kinaba: #include <complex> 91eacbb0eb 2017-07-22 kinaba: #include <queue> 91eacbb0eb 2017-07-22 kinaba: #include <stack> 91eacbb0eb 2017-07-22 kinaba: #include <cmath> 91eacbb0eb 2017-07-22 kinaba: #include <cassert> 91eacbb0eb 2017-07-22 kinaba: #include <tuple> 91eacbb0eb 2017-07-22 kinaba: using namespace std; 91eacbb0eb 2017-07-22 kinaba: typedef long long LL; 91eacbb0eb 2017-07-22 kinaba: typedef complex<double> CMP; 91eacbb0eb 2017-07-22 kinaba: 91eacbb0eb 2017-07-22 kinaba: class CanidsSeesaw { public: 91eacbb0eb 2017-07-22 kinaba: vector <int> construct(vector <int> wolf, vector <int> fox, int k) 91eacbb0eb 2017-07-22 kinaba: { 91eacbb0eb 2017-07-22 kinaba: partial_sum(wolf.begin(), wolf.end(), wolf.begin()); 91eacbb0eb 2017-07-22 kinaba: 91eacbb0eb 2017-07-22 kinaba: vector<pair<int, int>> fox_idx; 91eacbb0eb 2017-07-22 kinaba: for (int i = 0; i < fox.size(); ++i) 91eacbb0eb 2017-07-22 kinaba: fox_idx.emplace_back(fox[i], i); 91eacbb0eb 2017-07-22 kinaba: 91eacbb0eb 2017-07-22 kinaba: sort(fox_idx.rbegin(), fox_idx.rend()); 91eacbb0eb 2017-07-22 kinaba: while (point_of(fox_idx, wolf) > k) { 91eacbb0eb 2017-07-22 kinaba: bool swapped = false; 91eacbb0eb 2017-07-22 kinaba: for(int i=0; i+1<fox_idx.size(); ++i) 91eacbb0eb 2017-07-22 kinaba: if (fox_idx[i] > fox_idx[i + 1]) 91eacbb0eb 2017-07-22 kinaba: { 91eacbb0eb 2017-07-22 kinaba: swap(fox_idx[i], fox_idx[i + 1]); 91eacbb0eb 2017-07-22 kinaba: swapped = true; 91eacbb0eb 2017-07-22 kinaba: break; 91eacbb0eb 2017-07-22 kinaba: } 91eacbb0eb 2017-07-22 kinaba: if (!swapped)break; 91eacbb0eb 2017-07-22 kinaba: } 91eacbb0eb 2017-07-22 kinaba: 91eacbb0eb 2017-07-22 kinaba: if (point_of(fox_idx, wolf) == k) { 91eacbb0eb 2017-07-22 kinaba: vector<int> idx; 91eacbb0eb 2017-07-22 kinaba: for (auto fi : fox_idx) 91eacbb0eb 2017-07-22 kinaba: idx.push_back(fi.second); 91eacbb0eb 2017-07-22 kinaba: return idx; 91eacbb0eb 2017-07-22 kinaba: } 91eacbb0eb 2017-07-22 kinaba: return vector<int>(); 91eacbb0eb 2017-07-22 kinaba: } 91eacbb0eb 2017-07-22 kinaba: 91eacbb0eb 2017-07-22 kinaba: int point_of(const vector<pair<int,int>>& fox_idx, const vector<int>& wolf_sum) { 91eacbb0eb 2017-07-22 kinaba: int score = 0, cur = 0; 91eacbb0eb 2017-07-22 kinaba: for (int i = 0; i < fox_idx.size(); ++i) { 91eacbb0eb 2017-07-22 kinaba: cur += fox_idx[i].first; 91eacbb0eb 2017-07-22 kinaba: if (cur > wolf_sum[i]) 91eacbb0eb 2017-07-22 kinaba: ++score; 91eacbb0eb 2017-07-22 kinaba: } 91eacbb0eb 2017-07-22 kinaba: return score; 91eacbb0eb 2017-07-22 kinaba: } 91eacbb0eb 2017-07-22 kinaba: }; 91eacbb0eb 2017-07-22 kinaba: 91eacbb0eb 2017-07-22 kinaba: // BEGIN CUT HERE 91eacbb0eb 2017-07-22 kinaba: #include <ctime> 91eacbb0eb 2017-07-22 kinaba: double start_time; string timer() 91eacbb0eb 2017-07-22 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 91eacbb0eb 2017-07-22 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 91eacbb0eb 2017-07-22 kinaba: { os << "{ "; 91eacbb0eb 2017-07-22 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 91eacbb0eb 2017-07-22 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 91eacbb0eb 2017-07-22 kinaba: void verify_case(const vector <int>& Expected, const vector <int>& Received) { 91eacbb0eb 2017-07-22 kinaba: bool ok = (Expected == Received); 91eacbb0eb 2017-07-22 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 91eacbb0eb 2017-07-22 kinaba: cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } 91eacbb0eb 2017-07-22 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 91eacbb0eb 2017-07-22 kinaba: #define END verify_case(_, CanidsSeesaw().construct(wolf, fox, k));} 91eacbb0eb 2017-07-22 kinaba: int main(){ 91eacbb0eb 2017-07-22 kinaba: 91eacbb0eb 2017-07-22 kinaba: CASE(0) 91eacbb0eb 2017-07-22 kinaba: int wolf_[] = {3,1}; 91eacbb0eb 2017-07-22 kinaba: vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); 91eacbb0eb 2017-07-22 kinaba: int fox_[] = {4,2}; 91eacbb0eb 2017-07-22 kinaba: vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); 91eacbb0eb 2017-07-22 kinaba: int k = 1; 91eacbb0eb 2017-07-22 kinaba: int __[] = {1, 0 }; 91eacbb0eb 2017-07-22 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 91eacbb0eb 2017-07-22 kinaba: END 91eacbb0eb 2017-07-22 kinaba: CASE(1) 91eacbb0eb 2017-07-22 kinaba: int wolf_[] = {1,3}; 91eacbb0eb 2017-07-22 kinaba: vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); 91eacbb0eb 2017-07-22 kinaba: int fox_[] = {4,2}; 91eacbb0eb 2017-07-22 kinaba: vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); 91eacbb0eb 2017-07-22 kinaba: int k = 1; 91eacbb0eb 2017-07-22 kinaba: vector <int> _; 91eacbb0eb 2017-07-22 kinaba: END 91eacbb0eb 2017-07-22 kinaba: CASE(2) 91eacbb0eb 2017-07-22 kinaba: int wolf_[] = {10,10,10,10,10,10,10,10,10,10}; 91eacbb0eb 2017-07-22 kinaba: vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); 91eacbb0eb 2017-07-22 kinaba: int fox_[] = {1,100,1,100,1,100,1,100,1,100}; 91eacbb0eb 2017-07-22 kinaba: vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); 91eacbb0eb 2017-07-22 kinaba: int k = 7; 91eacbb0eb 2017-07-22 kinaba: int __[] = {0, 2, 4, 1, 6, 3, 5, 7, 9, 8 }; 91eacbb0eb 2017-07-22 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 91eacbb0eb 2017-07-22 kinaba: END 91eacbb0eb 2017-07-22 kinaba: CASE(3) 91eacbb0eb 2017-07-22 kinaba: int wolf_[] = {10,10,10,10,10,10,10,10,10,10}; 91eacbb0eb 2017-07-22 kinaba: vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); 91eacbb0eb 2017-07-22 kinaba: int fox_[] = {1,100,1,100,1,100,1,100,1,100}; 91eacbb0eb 2017-07-22 kinaba: vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); 91eacbb0eb 2017-07-22 kinaba: int k = 4; 91eacbb0eb 2017-07-22 kinaba: vector <int> _; 91eacbb0eb 2017-07-22 kinaba: END 91eacbb0eb 2017-07-22 kinaba: CASE(4) 91eacbb0eb 2017-07-22 kinaba: int wolf_[] = {2}; 91eacbb0eb 2017-07-22 kinaba: vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); 91eacbb0eb 2017-07-22 kinaba: int fox_[] = {1}; 91eacbb0eb 2017-07-22 kinaba: vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); 91eacbb0eb 2017-07-22 kinaba: int k = 0; 91eacbb0eb 2017-07-22 kinaba: int __[] = {0 }; 91eacbb0eb 2017-07-22 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 91eacbb0eb 2017-07-22 kinaba: END 91eacbb0eb 2017-07-22 kinaba: /* 91eacbb0eb 2017-07-22 kinaba: CASE(5) 91eacbb0eb 2017-07-22 kinaba: int wolf_[] = ; 91eacbb0eb 2017-07-22 kinaba: vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); 91eacbb0eb 2017-07-22 kinaba: int fox_[] = ; 91eacbb0eb 2017-07-22 kinaba: vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); 91eacbb0eb 2017-07-22 kinaba: int k = ; 91eacbb0eb 2017-07-22 kinaba: int __[] = ; 91eacbb0eb 2017-07-22 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 91eacbb0eb 2017-07-22 kinaba: END 91eacbb0eb 2017-07-22 kinaba: CASE(6) 91eacbb0eb 2017-07-22 kinaba: int wolf_[] = ; 91eacbb0eb 2017-07-22 kinaba: vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); 91eacbb0eb 2017-07-22 kinaba: int fox_[] = ; 91eacbb0eb 2017-07-22 kinaba: vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); 91eacbb0eb 2017-07-22 kinaba: int k = ; 91eacbb0eb 2017-07-22 kinaba: int __[] = ; 91eacbb0eb 2017-07-22 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); 91eacbb0eb 2017-07-22 kinaba: END 91eacbb0eb 2017-07-22 kinaba: */ 91eacbb0eb 2017-07-22 kinaba: } 91eacbb0eb 2017-07-22 kinaba: // END CUT HERE