47cb6fde79 2013-06-08 kinaba: #include <iostream> 47cb6fde79 2013-06-08 kinaba: #include <sstream> 47cb6fde79 2013-06-08 kinaba: #include <iomanip> 47cb6fde79 2013-06-08 kinaba: #include <vector> 47cb6fde79 2013-06-08 kinaba: #include <string> 47cb6fde79 2013-06-08 kinaba: #include <map> 47cb6fde79 2013-06-08 kinaba: #include <set> 47cb6fde79 2013-06-08 kinaba: #include <algorithm> 47cb6fde79 2013-06-08 kinaba: #include <numeric> 47cb6fde79 2013-06-08 kinaba: #include <iterator> 47cb6fde79 2013-06-08 kinaba: #include <functional> 47cb6fde79 2013-06-08 kinaba: #include <complex> 47cb6fde79 2013-06-08 kinaba: #include <queue> 47cb6fde79 2013-06-08 kinaba: #include <stack> 47cb6fde79 2013-06-08 kinaba: #include <cmath> 47cb6fde79 2013-06-08 kinaba: #include <cassert> 47cb6fde79 2013-06-08 kinaba: using namespace std; 47cb6fde79 2013-06-08 kinaba: typedef long long LL; 47cb6fde79 2013-06-08 kinaba: typedef long double LD; 47cb6fde79 2013-06-08 kinaba: typedef complex<double> CMP; 47cb6fde79 2013-06-08 kinaba: 47cb6fde79 2013-06-08 kinaba: class SurveillanceSystem { public: 47cb6fde79 2013-06-08 kinaba: string getContainerInfo(string containers, vector <int> reports, int L) 47cb6fde79 2013-06-08 kinaba: { 47cb6fde79 2013-06-08 kinaba: const int N = containers.size(); 47cb6fde79 2013-06-08 kinaba: 47cb6fde79 2013-06-08 kinaba: map< int, vector<int> > seen_to_pos; 47cb6fde79 2013-06-08 kinaba: for(int s=0; s+L<=N; ++s) 47cb6fde79 2013-06-08 kinaba: seen_to_pos[count(containers.begin()+s, containers.begin()+s+L, 'X')].push_back(s); 47cb6fde79 2013-06-08 kinaba: 47cb6fde79 2013-06-08 kinaba: map<int,int> seen_to_cnt; 47cb6fde79 2013-06-08 kinaba: for(int i=0; i<reports.size(); ++i) 47cb6fde79 2013-06-08 kinaba: seen_to_cnt[reports[i]]++; 47cb6fde79 2013-06-08 kinaba: 47cb6fde79 2013-06-08 kinaba: string result(N, '-'); 47cb6fde79 2013-06-08 kinaba: for(map<int,int>::iterator it=seen_to_cnt.begin(); it!=seen_to_cnt.end(); ++it) 47cb6fde79 2013-06-08 kinaba: { 47cb6fde79 2013-06-08 kinaba: int s = it->first; 47cb6fde79 2013-06-08 kinaba: int c = it->second; 47cb6fde79 2013-06-08 kinaba: vector<int>& p = seen_to_pos[s]; 47cb6fde79 2013-06-08 kinaba: mask(N, L, p, c, result); 47cb6fde79 2013-06-08 kinaba: } 47cb6fde79 2013-06-08 kinaba: return result; 47cb6fde79 2013-06-08 kinaba: } 47cb6fde79 2013-06-08 kinaba: 47cb6fde79 2013-06-08 kinaba: // May/must choose |K| ranges out of |p|. Update |result|. 47cb6fde79 2013-06-08 kinaba: void mask(int N, int L, vector<int>& p, int K, string& result) 47cb6fde79 2013-06-08 kinaba: { 47cb6fde79 2013-06-08 kinaba: assert(K > 0); 47cb6fde79 2013-06-08 kinaba: sort(p.begin(), p.end()); 47cb6fde79 2013-06-08 kinaba: 47cb6fde79 2013-06-08 kinaba: // Any range can be watched. 47cb6fde79 2013-06-08 kinaba: for(int i=0; i<p.size(); ++i) { 47cb6fde79 2013-06-08 kinaba: for(int x=p[i]; x<p[i]+L; ++x) 47cb6fde79 2013-06-08 kinaba: if(result[x] == '-') 47cb6fde79 2013-06-08 kinaba: result[x] = '?'; 47cb6fde79 2013-06-08 kinaba: } 47cb6fde79 2013-06-08 kinaba: 47cb6fde79 2013-06-08 kinaba: // Do "always" check. 47cb6fde79 2013-06-08 kinaba: for(int x=0; x<N; ++x) { 47cb6fde79 2013-06-08 kinaba: int cover = 0; 47cb6fde79 2013-06-08 kinaba: for(int i=0; i<p.size(); ++i) 47cb6fde79 2013-06-08 kinaba: if(p[i]<=x && x<p[i]+L) 47cb6fde79 2013-06-08 kinaba: ++cover; 47cb6fde79 2013-06-08 kinaba: // If |x| is covered by some range but avoiding them leaves <K... 47cb6fde79 2013-06-08 kinaba: if(cover && (p.size()-cover) < K) 47cb6fde79 2013-06-08 kinaba: result[x] = '+'; 47cb6fde79 2013-06-08 kinaba: } 47cb6fde79 2013-06-08 kinaba: } 47cb6fde79 2013-06-08 kinaba: }; 47cb6fde79 2013-06-08 kinaba: 47cb6fde79 2013-06-08 kinaba: // BEGIN CUT HERE 47cb6fde79 2013-06-08 kinaba: #include <ctime> 47cb6fde79 2013-06-08 kinaba: double start_time; string timer() 47cb6fde79 2013-06-08 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 47cb6fde79 2013-06-08 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 47cb6fde79 2013-06-08 kinaba: { os << "{ "; 47cb6fde79 2013-06-08 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 47cb6fde79 2013-06-08 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 47cb6fde79 2013-06-08 kinaba: void verify_case(const string& Expected, const string& Received) { 47cb6fde79 2013-06-08 kinaba: bool ok = (Expected == Received); 47cb6fde79 2013-06-08 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 47cb6fde79 2013-06-08 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 47cb6fde79 2013-06-08 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 47cb6fde79 2013-06-08 kinaba: #define END verify_case(_, SurveillanceSystem().getContainerInfo(containers, reports, L));} 47cb6fde79 2013-06-08 kinaba: int main(){ 47cb6fde79 2013-06-08 kinaba: 47cb6fde79 2013-06-08 kinaba: CASE(0) 47cb6fde79 2013-06-08 kinaba: string containers = "-X--XX"; 47cb6fde79 2013-06-08 kinaba: int reports_[] = {1, 2}; 47cb6fde79 2013-06-08 kinaba: vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*reports_)); 47cb6fde79 2013-06-08 kinaba: int L = 3; 47cb6fde79 2013-06-08 kinaba: string _ = "??++++"; 47cb6fde79 2013-06-08 kinaba: END 47cb6fde79 2013-06-08 kinaba: CASE(1) 47cb6fde79 2013-06-08 kinaba: string containers = "-XXXXX-"; 47cb6fde79 2013-06-08 kinaba: int reports_[] = {2}; 47cb6fde79 2013-06-08 kinaba: vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*reports_)); 47cb6fde79 2013-06-08 kinaba: int L = 3; 47cb6fde79 2013-06-08 kinaba: string _ = "???-???"; 47cb6fde79 2013-06-08 kinaba: END 47cb6fde79 2013-06-08 kinaba: CASE(2) 47cb6fde79 2013-06-08 kinaba: string containers = "------X-XX-"; 47cb6fde79 2013-06-08 kinaba: int reports_[] = {3, 0, 2, 0}; 47cb6fde79 2013-06-08 kinaba: vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*reports_)); 47cb6fde79 2013-06-08 kinaba: int L = 5; 47cb6fde79 2013-06-08 kinaba: string _ = "++++++++++?"; 47cb6fde79 2013-06-08 kinaba: END 47cb6fde79 2013-06-08 kinaba: CASE(3) 47cb6fde79 2013-06-08 kinaba: string containers = "-XXXXX---X--"; 47cb6fde79 2013-06-08 kinaba: int reports_[] = {2, 1, 0, 1}; 47cb6fde79 2013-06-08 kinaba: vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*reports_)); 47cb6fde79 2013-06-08 kinaba: int L = 3; 47cb6fde79 2013-06-08 kinaba: string _ = "???-??++++??"; 47cb6fde79 2013-06-08 kinaba: END 47cb6fde79 2013-06-08 kinaba: CASE(4) 47cb6fde79 2013-06-08 kinaba: string containers = "-XX--X-XX-X-X--X---XX-X---XXXX-----X"; 47cb6fde79 2013-06-08 kinaba: int reports_[] = {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}; 47cb6fde79 2013-06-08 kinaba: vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*reports_)); 47cb6fde79 2013-06-08 kinaba: int L = 7; 47cb6fde79 2013-06-08 kinaba: string _ = "???++++?++++++++++++++++++++??????--"; 47cb6fde79 2013-06-08 kinaba: END 47cb6fde79 2013-06-08 kinaba: /* 47cb6fde79 2013-06-08 kinaba: CASE(5) 47cb6fde79 2013-06-08 kinaba: string containers = ; 47cb6fde79 2013-06-08 kinaba: int reports_[] = ; 47cb6fde79 2013-06-08 kinaba: vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*reports_)); 47cb6fde79 2013-06-08 kinaba: int L = ; 47cb6fde79 2013-06-08 kinaba: string _ = ; 47cb6fde79 2013-06-08 kinaba: END 47cb6fde79 2013-06-08 kinaba: CASE(6) 47cb6fde79 2013-06-08 kinaba: string containers = ; 47cb6fde79 2013-06-08 kinaba: int reports_[] = ; 47cb6fde79 2013-06-08 kinaba: vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*reports_)); 47cb6fde79 2013-06-08 kinaba: int L = ; 47cb6fde79 2013-06-08 kinaba: string _ = ; 47cb6fde79 2013-06-08 kinaba: END 47cb6fde79 2013-06-08 kinaba: */ 47cb6fde79 2013-06-08 kinaba: } 47cb6fde79 2013-06-08 kinaba: // END CUT HERE