/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Wrong Answer 3ms 404.0 KiB

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define bug(a) cout<< #a << " : " << a <<endl;
#define bug2(a, b) cout<< #a << " : " << a  << " " << #b << " : " << b << endl;

void solve(int cs){
    int n, k;
    cin >> n >> k;
    string s;
    if(n == 0){
        return;
    }
    cin >> s;
    if(k == n){
        cout << 0 << '\n';
        return;
    }
    vector<int> idx[10];
    for(int i = 0;i < n;i++){
        idx[s[i] - '0'].push_back(i);
    }
    for(int i = 0;i <= 9;i++){
        sort(idx[i].rbegin(), idx[i].rend());
    }
    // vector<bool> ok(n, true);
    string ans = "";
    int cur_pos = -1;
    int sz = n - k;
    int cnt = 0;
    while(k && ans.size() < sz){
        for(int i = 9;i >= 0;i--){
            while(idx[i].size() && idx[i].back() <= cur_pos) idx[i].pop_back();
            if(idx[i].size()){
                int b = idx[i].back();
                int to_del = 1000;
                if(cur_pos == -1) to_del = b;
                else to_del = (b - cur_pos) - 1;
                if(ans.size() + (n - b) >= sz && k >= to_del){
                    ans += i + '0';
                    //bug(ans)
                    cur_pos = b;
                    //bug2(k, (b - cur_pos))
                    k -= to_del;
//                    bug2(k, b)
//                    bug(ans.size())
                    idx[i].pop_back();
                    if(ans.size() == sz) break;
                }
            }
        }
    }
    while(ans.size() < sz){
        cur_pos++;
        ans += s[cur_pos];
    }
    cout << ans << '\n';

}


int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    cout.tie(0);

    int tc = 1;
    cin >> tc;

    for(int cs = 1; cs <= tc; cs++){
        solve(cs);
    }
}

Information

Submit By
Type
Submission
Problem
P1006 Remove K Digits
Contest
Sylhet ICPC 2024 Collaborative Challenge: Episode 2
Language
C++17 (G++ 13.2.0)
Submit At
2024-10-30 11:47:08
Judged At
2024-11-11 02:34:50
Judged By
Score
0
Total Time
3ms
Peak Memory
404.0 KiB