Time Limit exceeded in test case 9.Can someone explain why?

Блог пользователя exelover

Автор exelover, история, 9 лет назад, По-английски

http://codeforces.me/contest/825/submission/28650576

Thanks in advance!

exelover
9 лет назад
1

Комментарии (1)

Написать комментарий?

redocyz

9 лет назад, скрыть # |

The problem is that you erase element from the vector O(n) times. and since the size of the vector is O(n), your time complexity would become O(N^2), which is too slow. You should use queue instead as you are only removing the top element.

Spoiler

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll int nc[26];
ll int nc2[26];

int main(){
    string s,t;
    queue<ll int> qpos;
    bool flag=true;
    bool com=false;
    ll int ans=0;
    cin>>s>>t;
    int qcnt=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='?'){
            qcnt++;
            qpos.push(i);
        }
        else {
            nc[s[i]-'a']++;
        }
    }
    for(ll int i=0;i<26;i++){
        nc2[i]=nc[i];
    }

    while(flag){
            for(ll int i=0;i<t.size();i++){
        if(nc[t[i]-'a']>0){
            nc[t[i]-'a']--;
        }
        else if(qcnt>0){
                qcnt--;
                int temp=qpos.front();
                qpos.pop();
                s[temp]=t[i];
        }
        else{flag=false;
        break;}
    }
    if (flag==true) ans++;
    }
    for(ll int i=0;i<s.size();i++){
        if(s[i]=='?'){cout<<'a';}
        else cout<<s[i];
    }



}

→ Ответить