This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MN = 100010;
ll N, msum;
int M;
string S[MN];
ll K[MN];
vector<string> T;
vector<ll> X;
void rem(char c, char o, ll x) {
vector<string> tt = T;
vector<ll> xx = X;
T.clear();
X.clear();
for(int i = (int)tt.size() - 1; i >= 0; i--) {
int cnt = 0;
for(int j = 0; j < tt[i].size(); j++) if(tt[i][j] == c) cnt++;
if(x) {
if(x >= xx[i] * cnt) {
if((int)tt[i].size() - cnt) {
T.push_back("");
T.back().push_back(o);
X.push_back(xx[i] * ((int)tt[i].size() - cnt));
}
x -= xx[i] * cnt;
}
else {
ll q = x / cnt;
if(q && (int)tt[i].size() - cnt) {
T.push_back("");
T.back().push_back(o);
X.push_back(q * ((int)tt[i].size() - cnt));
}
x -= q * cnt;
xx[i] -= q;
string tmp;
cnt = 0;
for(int j = (int)tt[i].size() - 1; j >= 0; j--) {
if(tt[i][j] == c) {
if(cnt >= x) tmp.push_back(c);
cnt++;
}
else tmp.push_back(o);
}
reverse(tmp.begin(), tmp.end());
T.push_back(tmp);
X.push_back(1);
if(xx[i] > 1) {
T.push_back(tt[i]);
X.push_back(xx[i] - 1);
}
x = 0;
}
}
else {
T.push_back(tt[i]);
X.push_back(xx[i]);
}
}
reverse(T.begin(), T.end());
reverse(X.begin(), X.end());
}
void rev() {
for(int i = 0; i < T.size(); i++) {
reverse(T[i].begin(), T[i].end());
}
reverse(T.begin(), T.end());
reverse(X.begin(), X.end());
}
void print() {
for(int i = 0; i < T.size(); i++) {
for(int j = 0; j < X[i]; j++) {
cout << T[i];
}
cout << ' ';
}
cout << endl;
}
bool check(ll x) {
//cout << x << endl;
T.clear();
X.clear();
if(x) {
T.push_back("M");
X.push_back(x);
}
for(int i = 0; i < M; i++) {
T.push_back(S[i]);
X.push_back(K[i]);
}
rem('M', 'F', x);
//print();
rev();
rem('F', 'M', 2 * N - 2 * msum);
rev();
//print();
ll sum = 0;
ll cnt = 0;
for(int i = 0; i < T.size(); i++) {
ll a = 0;
ll b = 0;
ll c = 0;
for(int j = 0; j < T[i].size(); j++) {
if(T[i][j] == 'M') a++;
else a--;
if(j % 2) b = min(b, a);
else c = min(c, a);
}
if(a >= 0) {
if(sum + (cnt % 2? c : b) < 0) return false;
if(X[i] > 1 && sum + a + ((cnt + (int)T[i].size()) % 2? c : b) < 0) return false;
sum += a * X[i];
cnt += X[i] * (int)T[i].size();
}
else {
if(sum + a * (X[i] - 1) + ((cnt + (X[i] - 1) * (int)T[i].size()) % 2? c : b) < 0) return false;
if(X[i] > 1 && sum + a * (X[i] - 2) + ((cnt + (X[i] - 2) * (int)T[i].size()) % 2? c : b) < 0) return false;
sum += a * X[i];
cnt += X[i] * (int)T[i].size();
}
}
return true;
}
int main() {
std::ios::sync_with_stdio(false);
cin >> N >> M;
for(int i = 0; i < M; i++) {
cin >> S[i] >> K[i];
int cnt = 0;
for(int j = 0; j < S[i].size(); j++) {
if(S[i][j] == 'M') cnt++;
}
msum += K[i] * cnt;
}
if(msum > N) {
cout << -1;
return 0;
}
ll s = 0, e = msum, p = -1;
while(s <= e) {
ll m = (s + e)>>1;
if(check(m)) {
p = m;
e = m - 1;
}
else s = m + 1;
}
cout << p;
}
Compilation message (stderr)
toilets.cpp: In function 'void rem(char, char, ll)':
toilets.cpp:24:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < tt[i].size(); j++) if(tt[i][j] == c) cnt++;
~~^~~~~~~~~~~~~~
toilets.cpp: In function 'void rev()':
toilets.cpp:73:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < T.size(); i++) {
~~^~~~~~~~~~
toilets.cpp: In function 'void print()':
toilets.cpp:81:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < T.size(); i++) {
~~^~~~~~~~~~
toilets.cpp: In function 'bool check(ll)':
toilets.cpp:116:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < T.size(); i++) {
~~^~~~~~~~~~
toilets.cpp:120:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < T[i].size(); j++) {
~~^~~~~~~~~~~~~
toilets.cpp: In function 'int main()':
toilets.cpp:152:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < S[i].size(); j++) {
~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |