Областная олимпиада по информатике 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 )
посмотреть в олимпиаде

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

  -4
2019-01-22 09:02:20.0 #

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

#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;

}

  -4
2019-03-31 22:24:05.0 #

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

пред. Правка 2   0
2019-12-15 11:17:02.0 #

пред. Правка 2   1
2019-12-15 11:16:37.0 #

  1
2022-10-05 21:58:00.0 #

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