Submission #498136

#	Time	Username	Problem	Language	Result	Execution time	Memory
498136		asandikci	Grudanje (COCI19_grudanje)	C++17	70 / 70	97 ms	14124 KiB

grudanje

#include"iostream"
#include"array"
#include"vector"
// #include"queue"
// #include"deque"
// #include"set"
// #include"map"
// #include"algorithm"
// #include"iomanip"
// #include"cstring"
// #include"cmath"
// #include"bitset"
// #define int long long
// __LINE__
using namespace std;  

const int maxn = 1e5;

string str,cur;
array<int,26> prefix[maxn+5];
vector<pair<int,int>> query;
int n,q;
vector<int> balls;

bool check(int x){
  cur = str;
  for(int i=0;i<x;i++){
    cur[balls[i]]='.';
  }
  for(int i=1;i<=n;i++){
    prefix[i]=prefix[i-1];
    if(cur[i]!='.')prefix[i][cur[i]-'a']++;
  }
  for(int i=0;i<q;i++){
    for(int j=0;j<26;j++){
      if(prefix[query[i].second][j]-prefix[query[i].first-1][j]>1){
        return false;
      }
    }
  }
  return true;
}

void solve(){
  cin >> str;
  n=str.length();
  str='#'+str;

  int a,b;
  cin >> q;
  for(int i=0;i<q;i++){
    cin >> a >> b;
    query.push_back({a,b});
  }
  for(int i=0;i<n;i++){
    cin >> a;
    balls.push_back(a);
  }
  int l=-1,r=n;
  while(l<r-1){
    int mid = (l+r)/2;
    if(check(mid)){
      r = mid;
    }
    else{
      l = mid;
    }
  }
  cout << r;
}

signed main(){
  ios::sync_with_stdio(false); cin.tie(0);
  // freopen("","r",stdin);freopen("","w",stdout);
  int t=1;
  // cin >> t;
  for(int i=1;i<=t;i++){
    // cout << "Case " << i << ":\n";
    solve();
    // cout <<"\n\n";
  }
}

• 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