Submission #811152

#	Time	Username	Problem	Language	Result	Execution time	Memory
811152		pcc	Grudanje (COCI19_grudanje)	C++14	70 / 70	214 ms	16808 KiB

grudanje

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second

string s;
int n,q;
vector<pii> req;

bool check(string &t){
	vector<int> pref[n+1];
	for(auto &i:pref)i = vector<int>(26,0);
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<26;j++)pref[i][j] = pref[i-1][j];
		if(t[i] != '#')pref[i][t[i]-'a']++;
	}
	//for(int i = 0;i<=n;i++)cout<<pref[i][0]<<' ';cout<<endl;
	for(auto &i:req){
		for(int j = 0;j<26;j++){
			if(pref[i.sc][j]-pref[i.fs-1][j] > 1)return false;
		}
	}
	return true;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>s;
	n = s.size();
	s = "#"+s;
	cin>>q;
	for(int i = 0;i<q;i++){
		int s,e;
		cin>>s>>e;
		req.push_back({s,e});
	}
	int mv[n+1] = {};
	mv[0] = 0;
	for(int i = 1;i<=n;i++)cin>>mv[i];
	int l = 0,r = n;
	while(l != r){
		int mid = (l+r)>>1;
		string t = s;
		for(int j = 1;j<=mid;j++)t[mv[j]] = '#';
		//cout<<mid<<":"<<t<<' '<<check(t)<<endl;
		if(check(t))r = mid;
		else l = mid+1;
	}
	cout<<l;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7