Областная олимпиада по информатике 2019 год

Задача D. Чередующие тренировки

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Алан очень сильно любит решать задачи по программированию и играть шахматы. В обоих сферах он хочет преуспеть, стать легендарным гроссмейстером. Айдос как опытный тренер предложил ему у него потренироваться.
   У Айдоса определенное расписание на каждый из следующих $n$ дней. В каждый из дней Айдос тренирует только один вид, либо программирование, либо шахматы. Алан хочет выбрать несколько подряд идущих дней для тренировки. Также Алан заметил, что если два дня подряд тренироваться в одной и той же сфере, то он устает, т.е. Алану надо чередовать шахматы и программирование. Помогите Алану выбрать максимальное количество подряд идущих дней так, чтобы он за этот период не устал тренироваться.

Формат входного файла

Первая строка входных данных содержит целое цисло $n$ ($1 <= n <= 2\cdot 10^5$) — количество тренировочных дней у Айдоса. Вторая строка содержит $n$ цифр $0$ или $1$ без пробелов — $i$-я цифра $0$ если в $i$-й день Айдос тренирует программирование, иначе Айдос тренирует шахматы.

Формат выходного файла

Выведите одно число — максимальное количество подряд идущих тренировочных дней для Алана.

Система оценки

В данной задаче 50 тестов, прохождение каждого теста оценивается в 2 балла:
Подзадача 1: 2 тестовых примера из условия
Подзадача 2: $n <= 3$. 13 тестов
Подзадача 3: $n <= 100$. 5 тестов
Подзадача 4: $n <= 5000$. 12 тестов
Подзадача 5: $n <= 200000$. 18 тестов

Примеры:

Вход

4 0
1010

Ответ

4

Вход

5 3
01011
1 3
2 5
4 5

Ответ

3

Замечание

В первом тесте Алан может все дни тренироваться. Во втором тесте Алан может тренироваться со 2-го по 4-й день: во 2-й день программирование, в 3-й день шахматы и в 4-й день программирование. Заметим, что первый, второй день Алан не может тренироваться, так как в эти дни только программирование и Алан сильно устанет. ( Temirulan Mussayev )

Комментарий/решение

Почему Ошибка Исполнения?

#include <bits/stdc++.h>

using namespace std;

int tl[200005];

int main(){

int n,m;

cin>>n>>m;

string s;

cin>>s;

for(int i=0;i<m;i++){

int l,r;

cin>>l>>r;

if(l>r){

swap(l,r);

}

tl[l]+=1;

tl[r+1]+=-1;

}

int rev=0;

for(int i=1;i<=n;i++){

rev+=tl[i];

if(rev%2==1){

if(s[i-1]=='0')s[i-1]='1';

else s[i-1]='0';

}

}

int mx=1,cnt=1;

for(int i=1;i<s.size();i++){

if(s[i]!=s[i-1]){

cnt++;

}

else{

mx=max(cnt,mx);

cnt=1;

}

}

mx=max(cnt,mx);

cnt=1;

cout<<mx;

}

показать/скрыть код

#include <bits/stdc++.h>
using namespace std;

//9 class

int main(){
    int n, ans = 0, k = 1;
    cin >> n;
    string s;
    cin >> s;
    for(int i = 1; i < s.length(); i++){
        if(s[i] != s[i-1]) k++;
        else{
            ans = max(ans, k);
            k = 1;
        }
    }
    ans = max(ans, k);
    cout << ans;
}

C++

Copy

показать/скрыть код

#include <bits/stdc++.h>

#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'

using namespace std;
using ll = long long;
using pii = pair<int, int>
using vvi = vt< vt<int> >

const int N = 1e6 + 5, mod = 1e9 + 7, inf = 1e18 + 7, B = 500, LIM = (1ll << 60), p = 31;
const double eps = 1e-6;

int get (string s) {
	int ans = 0;
	int i = 0;
	while (i < sz(s)) {
		int j = i, c = s[i] - 48;
		while (j + 1 < sz(s) && (s[j + 1] - 48) == (c ^ 1)) j++, c ^= 1;
		ans = max(ans, j - i + 1);
		i = j + 1;
	}
	return ans;
}

void solve () {
	int n, q;
	string s;
	cin >> n >> q >> s;
	vt<int> p(n + 5, 0);
	for (int i = 1; i <= q; i++) {
		int l, r;
		cin >> l >> r;
		p[l]++;
		p[r + 1]--;
	}
	partial_sum(all(p), p.begin());
	for (int i = 1; i <= n; i++) s[i - 1] ^= (p[i] & 1);
	cout << get(s);
	cout << '\n';
}

bool testcases = 0;

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int test = 1;
    if (testcases) cin >> test;
    for (int cs = 1; cs <= test; cs++) {
        solve();
    }
}

C++

Copy