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
Submission Time | |
---|---|
Task | D - 語呂合わせ |
User | noy72 |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 2953 Byte |
Status | AC |
Exec Time | 15 ms |
Memory | 384 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 40 / 40 | 60 / 60 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt |
Subtask1 | sample-02.txt, sample-03.txt, sample-04.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt |
Subtask2 | sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample-01.txt | AC | 1 ms | 256 KB |
sample-02.txt | AC | 1 ms | 256 KB |
sample-03.txt | AC | 1 ms | 256 KB |
sample-04.txt | AC | 1 ms | 256 KB |
subtask1-01.txt | AC | 1 ms | 256 KB |
subtask1-02.txt | AC | 1 ms | 256 KB |
subtask1-03.txt | AC | 1 ms | 256 KB |
subtask1-04.txt | AC | 1 ms | 256 KB |
subtask1-05.txt | AC | 1 ms | 256 KB |
subtask1-06.txt | AC | 1 ms | 256 KB |
subtask1-07.txt | AC | 1 ms | 256 KB |
subtask1-08.txt | AC | 1 ms | 256 KB |
subtask1-09.txt | AC | 1 ms | 256 KB |
subtask1-10.txt | AC | 1 ms | 256 KB |
subtask1-11.txt | AC | 1 ms | 256 KB |
subtask1-12.txt | AC | 1 ms | 256 KB |
subtask1-13.txt | AC | 1 ms | 256 KB |
subtask1-14.txt | AC | 1 ms | 256 KB |
subtask1-15.txt | AC | 1 ms | 256 KB |
subtask1-16.txt | AC | 1 ms | 256 KB |
subtask1-17.txt | AC | 1 ms | 256 KB |
subtask1-18.txt | AC | 1 ms | 256 KB |
subtask1-19.txt | AC | 1 ms | 256 KB |
subtask1-20.txt | AC | 1 ms | 256 KB |
subtask2-01.txt | AC | 2 ms | 256 KB |
subtask2-02.txt | AC | 4 ms | 256 KB |
subtask2-03.txt | AC | 5 ms | 256 KB |
subtask2-04.txt | AC | 6 ms | 256 KB |
subtask2-05.txt | AC | 4 ms | 256 KB |
subtask2-06.txt | AC | 4 ms | 256 KB |
subtask2-07.txt | AC | 12 ms | 256 KB |
subtask2-08.txt | AC | 2 ms | 256 KB |
subtask2-09.txt | AC | 15 ms | 384 KB |
subtask2-10.txt | AC | 10 ms | 256 KB |
subtask2-11.txt | AC | 10 ms | 256 KB |
subtask2-12.txt | AC | 5 ms | 256 KB |
subtask2-13.txt | AC | 5 ms | 256 KB |
subtask2-14.txt | AC | 7 ms | 256 KB |
subtask2-15.txt | AC | 5 ms | 256 KB |
subtask2-16.txt | AC | 5 ms | 256 KB |
subtask2-17.txt | AC | 1 ms | 256 KB |
subtask2-18.txt | AC | 10 ms | 256 KB |
subtask2-19.txt | AC | 8 ms | 256 KB |
subtask2-20.txt | AC | 9 ms | 256 KB |