Submission #576499


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(),(c).end()
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define iter(c) __typeof((c).begin())
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
#define mem(a) memset(a,0,sizeof(a))
#define pd(a) printf("%.10f\n",a)
#define pb(a) push_back(a)
#define in(a) insert(a)
#define pi M_PI
#define R cin>>
#define F first
#define S second
#define C class
#define ll long long
#define ln cout<<'\n'
#define _(_1,_2,_3,N,...)N
#define pr(...) _(__VA_ARGS__,pr3,pr2,pr1)(__VA_ARGS__)
template<C T>void pr1(T a){cout<<a;ln;}
template<C T,C T2>void pr2(T a,T2 b){cout<<a<<' '<<b;ln;}
template<C T,C T2,C T3>void pr3(T a,T2 b,T3 c){cout<<a<<' '<<b<<' '<<c;ln;}
template<C T>void PR(T a,int n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
bool check(int n,int m,int x,int y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<60,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

int n,m;
const int MAX_V=100000;
vector<vector<int> > g;
int level[MAX_V],iter[MAX_V];

void add_edge(int from,int to){
  g[from].push_back(to);
}

vector<int>  bipartiteMatching() {
    int nleft = g.size(), nright = 0;
    for(int i=0; i<g.size(); i++) {
      vector<int> es=g[i];
      if(es.size()) nright = max(nright, *max_element(es.begin(), es.end()) + 1);
    }
    vector<int> matchL(nleft, -1), matchR(nright, -1), prev(nleft), seen(nleft, -1);
    for(int i=0; i<nleft; i++) {
      vector<int> stk; stk.push_back(i);
      seen[i] = i; prev[i] = -1;
      while(!stk.empty()) {
        int v = stk.back(); stk.pop_back();
        for(int k=0; k<g[v].size(); k++) {
          int u = g[v][k];
          int j = matchR[u];
          if(j == -1) {
            while(v != -1) {
              matchR[u] = v;
              swap(u, matchL[v]);
              v = prev[v];
            }
            goto break_;
          }else if(seen[j] < i) {
            seen[j] = i; prev[j] = v;
            stk.push_back(j);
          }
        }
      }
    break_:;
    }
    return matchL;
}

int k;
void init() {
  vector<int> a;
  for(int i=0; i<=k; i++) g.pb(a);
}
map<string,int> ma;
map<int,string> mb;
int S(){return ma.size();}
void M(string s) {
  if(!ma.count(s)) {
    int x=S();
    ma[s]=x;
    mb[x]=s;
  }
}

void Main() {
  int T;
  cin >> k >> T;
  init();
  set<int> se[k+1];
  while(T--) {
    string s,t;
    cin >> s >> t;
    set<int> te[k+1];
    if(s.size()==1) {
      M(t);
      te[s[0]-'0'].in(ma[t]);
    } else if(s.size()==2) {
      REP(i,1,t.size()) {
        string x=t.substr(0,i),y=t.substr(i);
        M(x);M(y);
        set<int> re[k+1];
        re[s[0]-'0'].in(ma[x]);
        re[s[1]-'0'].in(ma[y]);
        bool f=1;
        REP(i,1,k+1) {
          if(re[i].size()>1) f=0;
        }
        if(!f) continue;
        REP(i,1,k+1) {
          if(re[i].size()) te[i].in(*re[i].begin());
        }
      }
    } else if(s.size()==3) {
      REP(i,1,t.size()-1) {
        REP(j,i+1,t.size()) {
          string x=t.substr(0,i),y=t.substr(i,j-i),z=t.substr(j);
          M(x);M(y);M(z);
          set<int> re[k+1];
          re[s[0]-'0'].in(ma[x]);
          re[s[1]-'0'].in(ma[y]);
          re[s[2]-'0'].in(ma[z]);
          bool f=1;
          REP(i,1,k+1) {
            if(re[i].size()>1) f=0;
          }
          if(!f) continue;
          REP(i,1,k+1) {
            if(re[i].size()) te[i].in(*re[i].begin());
          }
        }
      }
    } else if(s.size()==4) {
      REP(i1,1,t.size()-2) 
      REP(i2,i1+1,t.size()-1)
      REP(i3,i2+1,t.size()) {
        string x1=t.substr(0,i1),x2=t.substr(i1,i2-i1),x3=t.substr(i2,i3-i2),x4=t.substr(i3);
        M(x1);M(x2);M(x3);M(x4);
        set<int> re[k+1];
        re[s[0]-'0'].in(ma[x1]);
        re[s[1]-'0'].in(ma[x2]);
        re[s[2]-'0'].in(ma[x3]);
        re[s[3]-'0'].in(ma[x4]);
        bool f=1;
        REP(i,1,k+1) {
          if(re[i].size()>1) f=0;
        }
        if(!f) continue;
        REP(i,1,k+1) {
          if(re[i].size()) te[i].in(*re[i].begin());
        }
      }
    } else if(s.size()==5) {
      REP(i1,1,t.size()-3) 
      REP(i2,i1+1,t.size()-2)
      REP(i3,i2+1,t.size()-1)
      REP(i4,i3+1,t.size()) {
        string x1=t.substr(0,i1),x2=t.substr(i1,i2-i1),x3=t.substr(i2,i3-i2),x4=t.substr(i3,i4-i3),x5=t.substr(i4);
        M(x1);M(x2);M(x3);M(x4);M(x5);
        set<int> re[k+1];
        re[s[0]-'0'].in(ma[x1]);
        re[s[1]-'0'].in(ma[x2]);
        re[s[2]-'0'].in(ma[x3]);
        re[s[3]-'0'].in(ma[x4]);
        re[s[4]-'0'].in(ma[x5]);
        bool f=1;
        REP(i,1,k+1) {
          if(re[i].size()>1) f=0;
        }
        if(!f) continue;
        REP(i,1,k+1) {
          if(re[i].size()) te[i].in(*re[i].begin());
        }
      }
    } else if(s.size()==6) {
      REP(i1,1,t.size()-4) 
      REP(i2,i1+1,t.size()-3)
      REP(i3,i2+1,t.size()-2)
      REP(i4,i3+1,t.size()-1)
      REP(i5,i4+1,t.size()) {
        string x1=t.substr(0,i1),x2=t.substr(i1,i2-i1),x3=t.substr(i2,i3-i2),x4=t.substr(i3,i4-i3),x5=t.substr(i4,i5-i4),x6=t.substr(i5);
        M(x1);M(x2);M(x3);M(x4);M(x5);M(x6);
        set<int> re[k+1];
        re[s[0]-'0'].in(ma[x1]);
        re[s[1]-'0'].in(ma[x2]);
        re[s[2]-'0'].in(ma[x3]);
        re[s[3]-'0'].in(ma[x4]);
        re[s[4]-'0'].in(ma[x5]);
        re[s[5]-'0'].in(ma[x6]);
        bool f=1;
        REP(i,1,k+1) {
          if(re[i].size()>1) f=0;
        }
        if(!f) continue;
        REP(i,1,k+1) {
          if(re[i].size()) te[i].in(*re[i].begin());
        }
      }
    } else if(s.size()==7) {
      REP(i1,1,t.size()-5) 
      REP(i2,i1+1,t.size()-4)
      REP(i3,i2+1,t.size()-3)
      REP(i4,i3+1,t.size()-2)
      REP(i5,i4+1,t.size()-1)
      REP(i6,i5+1,t.size()) {
        string x1=t.substr(0,i1),x2=t.substr(i1,i2-i1),x3=t.substr(i2,i3-i2),x4=t.substr(i3,i4-i3),x5=t.substr(i4,i5-i4),x6=t.substr(i5,i6-i5),x7=t.substr(i6);
        M(x1);M(x2);M(x3);M(x4);M(x5);M(x6);M(x7);
        set<int> re[k+1];
        re[s[0]-'0'].in(ma[x1]);
        re[s[1]-'0'].in(ma[x2]);
        re[s[2]-'0'].in(ma[x3]);
        re[s[3]-'0'].in(ma[x4]);
        re[s[4]-'0'].in(ma[x5]);
        re[s[5]-'0'].in(ma[x6]);
        re[s[6]-'0'].in(ma[x7]);
        bool f=1;
        REP(i,1,k+1) {
          if(re[i].size()>1) f=0;
        }
        if(!f) continue;
        REP(i,1,k+1) {
          if(re[i].size()) te[i].in(*re[i].begin());
        }
      }
    } else if(s.size()==8) {
      REP(i1,1,t.size()-6) 
      REP(i2,i1+1,t.size()-5)
      REP(i3,i2+1,t.size()-4)
      REP(i4,i3+1,t.size()-3)
      REP(i5,i4+1,t.size()-2)
      REP(i6,i5+1,t.size()-1)
      REP(i7,i6+1,t.size()) {
        string x1=t.substr(0,i1),x2=t.substr(i1,i2-i1),x3=t.substr(i2,i3-i2),x4=t.substr(i3,i4-i3),x5=t.substr(i4,i5-i4),x6=t.substr(i5,i6-i5),x7=t.substr(i6,i5-i6),x8=t.substr(i7);
        M(x1);M(x2);M(x3);M(x4);M(x5);M(x6);M(x7);M(x8);
        set<int> re[k+1];
        re[s[0]-'0'].in(ma[x1]);
        re[s[1]-'0'].in(ma[x2]);
        re[s[2]-'0'].in(ma[x3]);
        re[s[3]-'0'].in(ma[x4]);
        re[s[4]-'0'].in(ma[x5]);
        re[s[5]-'0'].in(ma[x6]);
        re[s[6]-'0'].in(ma[x7]);
        re[s[7]-'0'].in(ma[x8]);
        bool f=1;
        REP(i,1,k+1) {
          if(re[i].size()>1) f=0;
        }
        if(!f) continue;
        REP(i,1,k+1) {
          if(re[i].size()) te[i].in(*re[i].begin());
        }
      }
    } else {
      REP(i1,1,t.size()-7) 
      REP(i2,i1+1,t.size()-6)
      REP(i3,i2+1,t.size()-5)
      REP(i4,i3+1,t.size()-4)
      REP(i5,i4+1,t.size()-3)
      REP(i6,i5+1,t.size()-2)
      REP(i7,i6+1,t.size()-1)
      REP(i8,i7+1,t.size()) {
        string x1=t.substr(0,i1),x2=t.substr(i1,i2-i1),x3=t.substr(i2,i3-i2),x4=t.substr(i3,i4-i3),x5=t.substr(i4,i5-i4),x6=t.substr(i5,i6-i5),x7=t.substr(i6,i5-i6),x8=t.substr(i7,i6-i7),x9=t.substr(i8);
        M(x1);M(x2);M(x3);M(x4);M(x5);M(x6);M(x7);M(x8);M(x9);
        set<int> re[k+1];
        re[s[0]-'0'].in(ma[x1]);
        re[s[1]-'0'].in(ma[x2]);
        re[s[2]-'0'].in(ma[x3]);
        re[s[3]-'0'].in(ma[x4]);
        re[s[4]-'0'].in(ma[x5]);
        re[s[5]-'0'].in(ma[x6]);
        re[s[6]-'0'].in(ma[x7]);
        re[s[7]-'0'].in(ma[x8]);
        re[s[8]-'0'].in(ma[x9]);
        bool f=1;
        REP(i,1,k+1) {
          if(re[i].size()>1) f=0;
        }
        if(!f) continue;
        REP(i,1,k+1) {
          if(re[i].size()) te[i].in(*re[i].begin());
        }
      }
    }
    set<int> re[k+1];
    REP(i,1,k+1) {
      if(!te[i].size()) continue;
      bool f=se[i].size();
      tr(it,te[i]) {
        if(!f||se[i].count(*it)) re[i].in(*it);
      }
      se[i]=re[i];
    }
  }
  REP(i,1,k+1) {
    tr(it,se[i]) add_edge(i,*it);
  }
  vector<int> res=bipartiteMatching();
  REP(i,1,res.size()) pr(mb[res[i]]);
}

int main() {
  ios::sync_with_stdio(0);cin.tie(0);
  Main();return 0;
}

Submission Info

Submission Time
Task D - 語呂合わせ
User kzyKT
Language C++ (GCC 4.9.2)
Score 0
Code Size 9247 Byte
Status WA
Exec Time 2035 ms
Memory 1060 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 0 / 40 0 / 60
Status
AC × 3
WA × 1
AC × 6
WA × 7
TLE × 10
AC × 12
WA × 11
TLE × 21
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 916 KB
sample-02.txt AC 27 ms 796 KB
sample-03.txt AC 29 ms 792 KB
sample-04.txt WA 26 ms 920 KB
subtask1-01.txt AC 167 ms 744 KB
subtask1-02.txt TLE 2034 ms 984 KB
subtask1-03.txt TLE 2032 ms 932 KB
subtask1-04.txt AC 82 ms 924 KB
subtask1-05.txt WA 25 ms 920 KB
subtask1-06.txt TLE 2034 ms 928 KB
subtask1-07.txt TLE 2033 ms 932 KB
subtask1-08.txt AC 29 ms 808 KB
subtask1-09.txt WA 27 ms 916 KB
subtask1-10.txt TLE 2034 ms 988 KB
subtask1-11.txt TLE 2033 ms 924 KB
subtask1-12.txt TLE 2035 ms 924 KB
subtask1-13.txt TLE 2035 ms 932 KB
subtask1-14.txt WA 45 ms 920 KB
subtask1-15.txt AC 142 ms 760 KB
subtask1-16.txt TLE 2035 ms 924 KB
subtask1-17.txt WA 26 ms 924 KB
subtask1-18.txt WA 341 ms 800 KB
subtask1-19.txt TLE 2034 ms 916 KB
subtask1-20.txt WA 26 ms 924 KB
subtask2-01.txt AC 472 ms 800 KB
subtask2-02.txt AC 487 ms 916 KB
subtask2-03.txt WA 1721 ms 1056 KB
subtask2-04.txt AC 997 ms 924 KB
subtask2-05.txt AC 1664 ms 924 KB
subtask2-06.txt TLE 2034 ms 1004 KB
subtask2-07.txt TLE 2034 ms 940 KB
subtask2-08.txt WA 315 ms 932 KB
subtask2-09.txt TLE 2035 ms 928 KB
subtask2-10.txt TLE 2034 ms 932 KB
subtask2-11.txt TLE 2033 ms 932 KB
subtask2-12.txt TLE 2034 ms 1056 KB
subtask2-13.txt TLE 2035 ms 1056 KB
subtask2-14.txt AC 30 ms 928 KB
subtask2-15.txt TLE 2034 ms 1060 KB
subtask2-16.txt WA 1355 ms 1048 KB
subtask2-17.txt WA 27 ms 912 KB
subtask2-18.txt TLE 2033 ms 936 KB
subtask2-19.txt TLE 2034 ms 928 KB
subtask2-20.txt TLE 2034 ms 936 KB