Submission #1165875

---

Source Code Expand

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const int INF = 2000000000;
using namespace std;

template < class BidirectionalIterator >
bool next_combination ( BidirectionalIterator first1 ,
        BidirectionalIterator last1 ,
        BidirectionalIterator first2 ,
        BidirectionalIterator last2 ){
    if (( first1 == last1 ) || ( first2 == last2 )) {
        return false ;
    }
    BidirectionalIterator m1 = last1 ;
    BidirectionalIterator m2 = last2 ; --m2;
    while (--m1 != first1 && !(* m1 < *m2 )){
    }
    bool result = (m1 == first1 ) && !(* first1 < *m2 );
    if (! result ) {
        while ( first2 != m2 && !(* m1 < * first2 )) {
            ++ first2 ;
        }
        first1 = m1;
        std :: iter_swap (first1 , first2 );
        ++ first1 ;
        ++ first2 ;
    }
    if (( first1 != last1 ) && ( first2 != last2 )) {
        m1 = last1 ; m2 = first2 ;
        while (( m1 != first1 ) && (m2 != last2 )) {
            std :: iter_swap (--m1 , m2 );
            ++ m2;
        }
        std :: reverse (first1 , m1 );
        std :: reverse (first1 , last1 );
        std :: reverse (m2 , last2 );
        std :: reverse (first2 , last2 );
    }
    return ! result ;
}

template < class BidirectionalIterator > bool next_combination ( BidirectionalIterator first , BidirectionalIterator middle , BidirectionalIterator last )
{
    return next_combination (first , middle , middle , last );
}

int k, n;
string s[55], w[55];

bool check(vector<int> v){
    string ans[10];
    rep(i,n){
        int c = 0;
        int cnt = 0;

        rep(j,s[i].size()){
            int p = s[i][j] - '1';
            assert(p < 10);

            int len = v[p];
            cnt += len;
            if(c + len > w[i].size()) return false;
            if(ans[p] == "") ans[p] = w[i].substr(c,len);
            else if(ans[p] != "" && ans[p] != w[i].substr(c,len)){
                return false;
            }
            c+=len;
        }
        if(cnt != w[i].size()) return false;
    }

    rep(i,k){
        cout << ans[i] << endl;
    }

    return true;
}

//要素vからr個取り出す組み合わせ
void func(vector<int> v, int r){
    do{
        do{
            if(check(v)){
                return;
            }
        }while(next_permutation(v.begin(), v.begin() + r));
    }while(next_combination(v.begin(), v.begin() + r, v.end()));
}

int main(){
    cin >> k >> n;

    rep(i,n) cin >> s[i] >> w[i];

    vector<int> v;
    rep(i,k) v.emplace_back(1);
    rep(i,k) v.emplace_back(2);
    rep(i,k) v.emplace_back(3);

    func(v,k);
}

Submission Info

Judge Result