Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1294 Accepted Submission(s): 442
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <vector> #include <queue> #include <map> #include <set> #include <stack> #include <algorithm> using namespace std; #define root 1,n,1 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define lr rt<<1 #define rr rt<<1|1 typedef long long LL; typedef pair<int,int>pii; #define X first #define Y second const int oo = 1e9+7; const double PI = acos(-1.0); const double eps = 1e-6 ; const int N = 1000010 ; const int mod = 1007; int t , n , head , tail ; int num[N] , nxt[N] , team_last[N] , belong[N]; void Init() { memset( nxt , -1 ,sizeof nxt ); memset( team_last , -1 ,sizeof team_last ); memset( belong , -1 ,sizeof belong ); head = tail = -1 ; } void Push1( int x ) { if( head == -1 ) { head = tail = x ; nxt[x] = -1 ; } else { nxt[tail] = x ; nxt[x] =-1 ; tail = x ; } } void Push2( int x , int last , int team ) { nxt[x] = nxt[last]; nxt[last] = x ; team_last[team] = x ; if( nxt[x] == -1 ) tail = x ; } void Run() { Init(); int x ; for( int i = 1 ; i <= t ; ++i ) { cin >> n ; for( int j = 0 ; j < n ; ++j ){ cin >> x ; belong[x] = i ; } } string s ; while( cin >> s ) { if( s[0] == ‘S‘ ) break ; else if( s[0] == ‘E‘ ) { cin >> x ; if( belong[x] == -1 ) Push1(x); else { if( team_last[belong[x]] == -1 ) Push1(x) , team_last[belong[x]] = x ; else Push2(x,team_last[belong[x]],belong[x]); } } else { cout << head << endl ; if( team_last[belong[head]] == head ) team_last[belong[head]] = -1 ; head = nxt[head] ; } } } int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL ios::sync_with_stdio(false); int _ , cas = 1 ; //cin >> _ ; while( cin >> t && t ) { cout << "Scenario #" << cas++ << endl ; Run(); cout << endl ; } }
原文:http://www.cnblogs.com/hlmark/p/4209822.html