Untitled

 avatar
unknown
c_cpp
2 years ago
2.3 kB
3
Indexable
#include <bits/stdc++.h>
#define endl '\n';
using namespace std;

int nums[100002];

string target;
string ret = "";    
int length;
int mi, ma;
char MI, MA;
int cnt;

void backtracking(int cur, bool flag){
    if(cur == length) {
        if(ret ==""){
            if(mi==0 && nums[0] == 0){
                ret = "-1";
                return;
            }
            ret = "#";
            cout << "#" << ++cnt << " ";
            for(int i = 0;i<length;i++){
                if(nums[i]==mi){
                    // ret += MI;
                    cout << MI;
                }
                else{
                    cout << MA;
                    // ret += MA;
                }
            }
            cout << '\n';
            return;
        }
        return;
    }

    int now = target[cur]-48;
    if(flag == false){
        if(now>=ma){
            if(now > ma){
                nums[cur] = ma;
                backtracking(cur+1, true);
                nums[cur] = -2;
            }
            else{
                nums[cur] = ma;
                backtracking(cur+1,  false);
                nums[cur] = mi;
                backtracking(cur+1,  true);
                nums[cur] = -2;
            }
        }
        else if(mi <= now && now < ma){
            if(mi == now){
                nums[cur] = mi;
                backtracking(cur+1, false);
                nums[cur] = -2;
            }    
            else{
                nums[cur] = mi;
                backtracking(cur+1, true);
                nums[cur] = -2;
            }
        }
        else{
            return;
        }
    }
    else{
        nums[cur] = ma;
        backtracking(cur+1,  true);
        nums[cur] = -2;
    }
    return;
}

int main(void){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        ret = "";
        cin >> target;
        cin >> mi >> ma;
        length = target.size();
        fill(nums,nums+length+1, -1);
        MI = char(mi+48); MA = char(ma+48);
        backtracking(0, false);
        if(ret==""){
            cout << "#" << ++cnt << " " << -1 << '\n';
        }
        else{
            continue;
            // cout << "#" << ++cnt << " " << ret << '\n';
        }
    }
}
Editor is loading...