Submission #1005029

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

struct MovingRuns {
	static const int NumColors = 2;
	struct Run {
		int color;
		int basePos;
		Run *linkL, *linkR;
	};
	vector<Run> runs;
	int offsets[NumColors];
	Run *head;
	priority_queue<pair<int, Run*>> pqs[NumColors][NumColors];
	void init(const vector<int> &A) {
		runs.clear();
		{
			int n = (int)A.size();
			int curL = 0;
			for(int i = 0; i <= n; i ++) {
				if(i == n || (i != 0 && A[i] != A[i - 1])) {
					runs.push_back(Run{ A[i - 1], curL, nullptr, nullptr });
					curL = i;
				}
			}
		}
		rep(i, runs.size()) {
			if(0 < i)
				runs[i].linkL = &runs[i - 1];
			if(i + 1 < (int)runs.size())
				runs[i].linkR = &runs[i + 1];
		}
		head = runs.empty() ? nullptr : &runs[0];
		rep(k, NumColors) {
			offsets[k] = 0;
			rep(l, NumColors)
				while(!pqs[k][l].empty()) pqs[k][l].pop();
		}
		rep(i, (int)runs.size() - 1) {
			int dist = getDist(&runs[i]);
			pqs[runs[i].color][runs[i + 1].color].push(make_pair(-dist, &runs[i]));
		}
	}

	int getDist(Run *x) const {
		Run *y = x->linkR;
		if(!y)
			return INF;
		return y->basePos - x->basePos + offsets[y->color] - offsets[x->color];
	}

	void moveToRight(int k) {
		++ offsets[k];
		rep(l, NumColors) {
			auto &pq = pqs[k][l];
			while(!pq.empty()) {
				int dist = -pq.top().first + offsets[l] - offsets[k];
				Run *run = pq.top().second;
				if(getDist(run) != dist) {
					pq.pop();
					continue;
				}
				if(dist > 0)
					break;
				assert(dist == 0);
				pq.pop();
				Run *l = run->linkL, *r = run->linkR;
				if(l != nullptr)
					l->linkR = r;
				else
					head = r;
				if(r != nullptr)
					r->linkL = l;
				run->linkL = run->linkR = nullptr;
				run->color = -1;
				if(l != nullptr && r != nullptr) {
					int dist = getDist(l);
					int d = dist - offsets[r->color] + offsets[l->color];
					pqs[l->color][r->color].push(make_pair(-d, l));
				}
			}
		}
	}

	void getResult(int n, vector<int> &colors) const {
		colors.assign(n, -1);
		int curL = 0, curColor = -1;
		for(const Run *x = head; ; x = x->linkR) {
			int pos = x == nullptr ? n : x->basePos + offsets[x->color],
				color = x == nullptr ? -1 : x->color;
			for(int i = curL; i < pos && i < n; ++ i)
				colors[i] = curColor;
			curL = pos, curColor = color;
			if(x == nullptr) break;
		}
	}
};

int main() {
	int N;
	while(~scanf("%d", &N)) {
		vector<int> A(N);
		for(int i = 0; i < N; ++ i)
			scanf("%d", &A[i]);
		char S[100000];
		scanf("%s", S);
		MovingRuns mr;
		int lo = 1, up = N;
		while(up - lo > 0) {
			int mid = (lo + up + 1) / 2;
			vector<int> colors(N);
			rep(i, N)
				colors[i] = A[i] >= mid;
			mr.init(colors);
			rep(i, N - 1) {
				if(S[i] == 'M') {
					mr.moveToRight(0);
				} else {
					mr.moveToRight(1);
				}
			}
			vector<int> result;
			mr.getResult(N, result);
			if(result[N - 1] == 1)
				lo = mid;
			else
				up = mid - 1;
		}
		printf("%d\n", lo);
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:111:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &A[i]);
                      ^
./Main.cpp:113:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", S);
                 ^

Judge Result