Basic Data Structure hdu 5929 双端队列+模拟+思维

Basic Data Structure

思维

1，如果有0，那么前面的只要有数即为1.
2，故只需统计最后一个0的位置和该位置后的1的数量，可以用下标求解。
3，要手写双端队列，不要有deque ，没法存位置下标信息。

/*

hello world!

Just do it!

start time:2022-05-02 10:41:09.361841

*/

// #pragma GCC optimize (2)
// #pragma G++ optimize (2)
#include 
#define zero(x) memset(x, 0, sizeof(x));
#define one(x) memset(x, -1, sizeof(x));
#define m_INF(x) memset(x, 0x3f, sizeof(x));
#define m_inf(x) memset(x, 0x3f, sizeof(x));
#define m_f_INF(x) memset(x, -0x3f, sizeof(x));
#define m_f_inf(x) memset(x, -0x3f, sizeof(x));
#define all(x) x.begin(), x.end()
#define endl "\n" 
#define fi first
#define se second
#define lbt(x) ((x)&(-x))
#define pb push_back

struct cmpl{ template  bool operator()(const A &a1, const B &b1) { return b1 < a1; } };
struct cmpg{ template  bool operator()(const A &a1, const B &b1) { return a1 < b1; } };
#define p_ql(x) priority_queue, cmpl>
#define p_qlp(x, y) priority_queue, vector>, cmpl>
#define p_qg(x) priority_queue, cmpg>
#define p_qgp(x, y) priority_queue, vector>, cmpg>
template bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
#define fo(i,from,to) for(int i=(from),ooo=(from)<(to)?1:-1,oooo=(to)+ooo;i!=oooo;i+=ooo)
#define fol(i,from,to) for(long long i=(from),ooo=(from)<(to)?1:-1,oooo=(to)+ooo;i!=oooo;i+=ooo)
#define foo(i,ooo) for(auto i=ooo.rbegin();i!=ooo.rend();++i)
#define foa(i,from,to) for(int i=(from),ooo=(to);i<=ooo;++i)
#define fos(i,from,to) for(int i=(from),ooo=(to);i>=ooo;--i)

using namespace std;

#ifndef LOCAL
#    define dbg(...) ;
#endif

#define itn int
#define int long long

#ifdef int
#define inf (0x3f3f3f3f3f3f3f3f)
#else
#define inf (0x3f3f3f3f)
#endif

typedef long long ll; typedef unsigned long long ull; typedef pair pii;
const int  dir[8][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}}, INF = 0x3f3f3f3f, f_inf = -1044266559, f_INF = -1044266559;
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int N = 2e6 + 10;
int n, m;

void init()
{
    
}
int q[N], hh = 1e6, tt = 1e6 - 1;
void solve()
{
	hh = 1e6, tt = 1e6 - 1;
    int t;
	cin >> t;
	int dr = 1;
	set st;
	while(t--) {
		string s;
		cin >> s;
		if(s == "PUSH") {
			int x;
			cin >> x;
			if(dr) {
				q[++tt] = x;
				if(x == 0) st.insert(tt);
			} else {
				q[--hh] = x;
				if(x == 0) st.insert(hh);
			}
		}else if(s == "POP") {
			if(dr) {
				if(q[tt] == 0) st.erase(tt);
				tt--;
			}else {
				if(q[hh] == 0) st.erase(hh);
				hh++;
			}
		} else if(s == "REVERSE") {
			dr = !dr;
		} else {
			// dbg(hh, tt, st, dr)
			if(hh > tt) cout << "Invalid.\n";
			// else if(tt == hh) {
			// 	cout << q[tt] << endl;
			// }
			else if(st.empty()) {
				if(tt - hh & 1) cout << "0\n";
				else cout << "1\n";
			}
			else if(dr) {
				if(*st.begin() == tt) { // 特判 ！！！ 是st.begin() !!!
					if(tt - hh & 1) cout << "1\n";
					else cout << "0\n";
				}else{
					if(*st.begin() - hh & 1) cout << "0\n";
					else cout << "1\n";
				}
			} else {
				if(*st.rbegin() == hh) {
					if(tt - hh & 1) cout << "1\n";
					else cout << "0\n";
				}else{
					if(tt - *st.rbegin() & 1) cout << "0\n";
					else cout << "1\n";
				}
			}
		}
	}
}
signed main()
{

#ifdef LOCAL
	freopen("read.in", "r", stdin);
	freopen("write.out", "w", stdout);
#endif

	std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);

	init();

    int t = 0, num2 = 0;

    // t = 1;

    if (!t) cin >> t;
    while (t--) {
        cout<<"Case #"<<++num2<<":\n";
		solve();
    }
    return 0;

	int num1 = 0;
	//while (scanf("%d", &n) !=-1 && n)
    while (cin >> n && n) {
        //cout<<"Case "<<++num1<<": ";
		solve();
    }
    return 0;

}