ALGORITHM NOTE Analyzing Login/Logout Records

Analyzing Login/Logout Records

2007.07.16 01:22 ACM/ICPC 2007

[問題] ACM/ICPC 国内予選2007: Problem B
[解説]
生徒と時間に関するbool値の２次元配列を埋めていく方法が安全で簡単です。
入力から各生徒のマシンごとのログイン・ログアウトの状況を記録していくのが多少面倒ですが、map を使うと便利だと思います。

コンテストではこの力任せ方法が妥当ですが、実際のシステムではこのようには実装しないでしょうね

。

001 #include 002 #include 003 #include 004 using namespace std; 005 #define PMAX 1000 // number of PC 006 #define SMAX 10000 // number of Student 007 #define TMAX 1260 008 009 int npc, nstudent; 010 bool record[SMAX+1][TMAX+1]; 011 012 void init(){ 013 for ( int i = 0; i <= nstudent; i++ ){ 014 for ( int t = 0; t <= TMAX; t++ ){ 015 record[i][t] = false; 016 } 017 } 018 } 019 020 void compute(){ 021 int q; cin >> q; 022 int total, s, e, m; 023 for ( int i = 0; i < q; i++ ){ 024 cin >> s >> e >> m; 025 total = 0; 026 for ( int t = s; t < e; t++ ){ 027 if ( record[m][t] ) total++; 028 } 029 cout << total << endl; 030 } 031 } 032 033 void fill( int student, int start, int end ){ 034 for ( int t = start; t < end; t++ ) record[student][t] = true; 035 } 036 037 bool input(){ 038 cin >> npc >> nstudent; 039 if ( npc == 0 && nstudent == 0 ) return false; 040 init(); 041 mapint, int>, int> login; 042 int r, t, pc, student, state; 043 cin >> r; 044 for ( int i = 0; i < r; i++ ){ 045 cin >> t >> pc >> student >> state; 046 if ( state == 1 ){ 047 login[make_pair(pc, student)] = t; 048 } else { 049 fill( student, login[make_pair(pc, student)], t ); 050 } 051 } 052 return true; 053 } 054 055 main(){ 056 while( input()) compute(); 057 }

スポンサーサイト