Submission #576261


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< int,int > P;
const int mod = 1e9+7;
const int inf = numeric_limits< int >::max()/3;

vector< string > v;
vector< string > w;
vector< string > s;
int k,n;

bool dfs(int m){
  if(n == m){
    return true;
  }else{
    string t = "";
    string nv = v[m];
    string nw = w[m];
    int p = 0;
    for(int i = 0;i < (int)nv.size();++i){
      if(s[nv[i] - '0'] == ""){
	for(int j = 2;j >= 0;--j){
	  if(p+j >= (int)nw.size()){
	    continue;
	  }else{
	    s[nv[i] - '0'] = nw.substr(p,j+1);
	    if(dfs(m))return true;
	    s[nv[i] - '0'] = "";
	  }
	}
	return false;
      }else{
	t += s[nv[i] - '0'];
	p += s[nv[i] - '0'].size();
      }
    }
    if(nw != t)return false;
    return dfs(m+1);
  }
}

int main(void){
  cin >> k >> n;
  s.resize(k+1);
  for(int i = 0;i < n;++i){
    string cv,cw;
    cin >> cv >> cw;
    v.push_back(cv);
    w.push_back(cw);
  }
  for(int i = 0;i <= k;++i){
    s[i] = "";
  }
  dfs(0);
  for(int i = 1;i <= k;++i){
    cout << s[i] << endl;
  }
  return 0;
}

Submission Info

Submission Time
Task D - 語呂合わせ
User Ashurnasirpal
Language C++ (GCC 4.9.2)
Score 100
Code Size 1135 Byte
Status AC
Exec Time 28 ms
Memory 932 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 40 / 40 60 / 60
Status
AC × 4
AC × 23
AC × 44
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 27 ms 796 KB
sample-02.txt AC 25 ms 920 KB
sample-03.txt AC 26 ms 796 KB
sample-04.txt AC 24 ms 920 KB
subtask1-01.txt AC 24 ms 924 KB
subtask1-02.txt AC 25 ms 812 KB
subtask1-03.txt AC 26 ms 800 KB
subtask1-04.txt AC 26 ms 796 KB
subtask1-05.txt AC 26 ms 796 KB
subtask1-06.txt AC 26 ms 928 KB
subtask1-07.txt AC 25 ms 920 KB
subtask1-08.txt AC 28 ms 928 KB
subtask1-09.txt AC 26 ms 920 KB
subtask1-10.txt AC 27 ms 796 KB
subtask1-11.txt AC 26 ms 800 KB
subtask1-12.txt AC 26 ms 732 KB
subtask1-13.txt AC 27 ms 924 KB
subtask1-14.txt AC 25 ms 928 KB
subtask1-15.txt AC 26 ms 796 KB
subtask1-16.txt AC 25 ms 924 KB
subtask1-17.txt AC 26 ms 804 KB
subtask1-18.txt AC 26 ms 808 KB
subtask1-19.txt AC 25 ms 808 KB
subtask1-20.txt AC 26 ms 800 KB
subtask2-01.txt AC 25 ms 932 KB
subtask2-02.txt AC 26 ms 804 KB
subtask2-03.txt AC 24 ms 848 KB
subtask2-04.txt AC 26 ms 804 KB
subtask2-05.txt AC 26 ms 920 KB
subtask2-06.txt AC 26 ms 808 KB
subtask2-07.txt AC 26 ms 804 KB
subtask2-08.txt AC 26 ms 808 KB
subtask2-09.txt AC 27 ms 772 KB
subtask2-10.txt AC 26 ms 916 KB
subtask2-11.txt AC 24 ms 808 KB
subtask2-12.txt AC 26 ms 932 KB
subtask2-13.txt AC 25 ms 928 KB
subtask2-14.txt AC 25 ms 928 KB
subtask2-15.txt AC 25 ms 932 KB
subtask2-16.txt AC 26 ms 812 KB
subtask2-17.txt AC 26 ms 932 KB
subtask2-18.txt AC 26 ms 800 KB
subtask2-19.txt AC 26 ms 932 KB
subtask2-20.txt AC 26 ms 804 KB