Submission #2140278
Source Code Expand
// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}
const int N = 1e5 + 10;
int n , a[N] , c[N];
char s[N];
bool check(int x) {
rep(i,0,n) c[i] = a[i] >= x;
set<pii> seg;
priority_queue<pair<int,pii> > q[2];
int cnt[2] = {0 , 0};
for(int i=0,j=0;i<n;i=j) {
for(j=i;j<n&&c[j]==c[i];++j);
seg.insert(mp(i , j - 1));
q[c[i]].push(mp(-(j - i) , mp(i , j - 1)));
}
rep(i,0,n-1) {
cnt[s[i] == 'M']++;
int p = s[i] == 'M' ? 0 : 1;
while(sz(q[p])) {
int x = -q[p].top().fi;
pii s = q[p].top().se;
if(!seg.count(s)) {
q[p].pop();
continue;
}
if(x + cnt[p] > cnt[p^1]) break;
q[p].pop();
seg.erase(s);
int l = s.fi , r = s.se;
//cout << i << " " << l << " " << r << endl;
auto it = seg.upper_bound(s);
if(it != seg.end()) {
r = it->se;
seg.erase(it);
}
it = seg.upper_bound(s);
if(it != seg.begin()) {
--it;
l = it->fi;
seg.erase(it);
}
c[l] = c[r] = p ^ 1;
seg.insert(mp(l , r));
q[c[l]].push(mp(-(r - l + 1) , mp(l , r)));
}
}
for(auto e : seg) {
int l = e.fi , r = e.se;
int p = c[l];
if(p) l -= cnt[1] , r -= cnt[0];
else r -= cnt[1] , l -= cnt[0];
if(l <= 0 && 0 <= r)
return p;
}
return true;
}
int main(){
scanf("%d",&n);
rep(i,0,n) scanf("%d",a + i);
scanf("%s",s);
int l = 1 , r = n + 1;
while(l + 1 < r) {
int mid = (l + r) >> 1;
(check(mid) ? l : r) = mid;
}
printf("%d\n",l);
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Compression |
User |
Y_UME |
Language |
C++14 (GCC 5.4.1) |
Score |
1400 |
Code Size |
2350 Byte |
Status |
AC |
Exec Time |
555 ms |
Memory |
5080 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:94:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:95:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
rep(i,0,n) scanf("%d",a + i);
^
./Main.cpp:96:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",s);
^
Judge Result
Set Name |
Sample |
subtask1 |
subtask2 |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
800 / 800 |
200 / 200 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt |
subtask1 |
sample_2.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 |
sample_1.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt |
All |
sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, 2_1.txt, 2_2.txt, sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_10.txt, subtask_3_11.txt, subtask_3_12.txt, subtask_3_13.txt, subtask_3_14.txt, subtask_3_15.txt, subtask_3_16.txt, subtask_3_17.txt, subtask_3_18.txt, subtask_3_19.txt, subtask_3_2.txt, subtask_3_20.txt, subtask_3_21.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt |
Case Name |
Status |
Exec Time |
Memory |
2_1.txt |
AC |
1 ms |
256 KB |
2_2.txt |
AC |
1 ms |
256 KB |
sample_1.txt |
AC |
1 ms |
256 KB |
sample_2.txt |
AC |
1 ms |
256 KB |
sample_3.txt |
AC |
1 ms |
256 KB |
sample_4.txt |
AC |
1 ms |
256 KB |
subtask_1.2_1.txt |
AC |
1 ms |
256 KB |
subtask_1.2_2.txt |
AC |
1 ms |
256 KB |
subtask_1_1.txt |
AC |
109 ms |
4864 KB |
subtask_1_10.txt |
AC |
102 ms |
4608 KB |
subtask_1_2.txt |
AC |
100 ms |
4736 KB |
subtask_1_3.txt |
AC |
99 ms |
4744 KB |
subtask_1_4.txt |
AC |
90 ms |
4320 KB |
subtask_1_5.txt |
AC |
20 ms |
768 KB |
subtask_1_6.txt |
AC |
105 ms |
4864 KB |
subtask_1_7.txt |
AC |
1 ms |
256 KB |
subtask_1_8.txt |
AC |
102 ms |
4864 KB |
subtask_1_9.txt |
AC |
101 ms |
4864 KB |
subtask_2_1.txt |
AC |
279 ms |
4472 KB |
subtask_2_10.txt |
AC |
262 ms |
4472 KB |
subtask_2_2.txt |
AC |
127 ms |
4472 KB |
subtask_2_3.txt |
AC |
285 ms |
4472 KB |
subtask_2_4.txt |
AC |
119 ms |
4600 KB |
subtask_2_5.txt |
AC |
1 ms |
256 KB |
subtask_2_6.txt |
AC |
1 ms |
256 KB |
subtask_2_7.txt |
AC |
1 ms |
256 KB |
subtask_2_8.txt |
AC |
294 ms |
4472 KB |
subtask_2_9.txt |
AC |
25 ms |
1280 KB |
subtask_3_1.txt |
AC |
555 ms |
4664 KB |
subtask_3_10.txt |
AC |
316 ms |
4864 KB |
subtask_3_11.txt |
AC |
515 ms |
5080 KB |
subtask_3_12.txt |
AC |
109 ms |
4884 KB |
subtask_3_13.txt |
AC |
109 ms |
4472 KB |
subtask_3_14.txt |
AC |
107 ms |
4868 KB |
subtask_3_15.txt |
AC |
102 ms |
4864 KB |
subtask_3_16.txt |
AC |
102 ms |
4864 KB |
subtask_3_17.txt |
AC |
102 ms |
4864 KB |
subtask_3_18.txt |
AC |
103 ms |
4736 KB |
subtask_3_19.txt |
AC |
106 ms |
4484 KB |
subtask_3_2.txt |
AC |
384 ms |
4472 KB |
subtask_3_20.txt |
AC |
106 ms |
4860 KB |
subtask_3_21.txt |
AC |
106 ms |
4872 KB |
subtask_3_3.txt |
AC |
49 ms |
872 KB |
subtask_3_4.txt |
AC |
457 ms |
4216 KB |
subtask_3_5.txt |
AC |
408 ms |
4332 KB |
subtask_3_6.txt |
AC |
444 ms |
4636 KB |
subtask_3_7.txt |
AC |
310 ms |
4868 KB |
subtask_3_8.txt |
AC |
332 ms |
4620 KB |
subtask_3_9.txt |
AC |
175 ms |
4864 KB |