QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#753397 | #9558. The Devil | ucup-team3931# | WA | 685ms | 166600kb | C++14 | 4.5kb | 2024-11-16 12:43:55 | 2024-11-16 12:44:04 |
Judging History
answer
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("Ofast","unroll-loops","inline")
#include<bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define MP make_pair
#define fi first
#define se second
#define ull unsigned ll
#define pii pair<ull,int>
using namespace std;
const int N=2e2+20,M=3e6+20,mod=1e9+9;
inline void Add(int &x,int y){x+=y;if(x>=mod) x-=mod;}
inline void Del(int &x,int y){x-=y;if(x<0) x+=mod;}
inline int del(int x,int y){x-=y;return x<0?x+mod:x;}
inline int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
const int Inf=1e18;
const pii bas=MP(1337,10007);
namespace mf{
int ecnt=1;
struct Edge{int v,f,w;}eg[M];
vector<int> e[M];
int n,s,t,d[M],cur[M];
bool vis[M];
inline void init(){n=s=t=0;ecnt=1;}
inline void add(int u,int v,int f,int w){
eg[++ecnt]=(Edge){v,f,w};
e[u].pb(ecnt);
}
inline void add_edge(int u,int v,int f,int w){add(u,v,f,w),add(v,u,0,-w);}
bool spfa(){
queue<int> q;
for(int i=0;i<=n;i++) d[i]=Inf;
d[s]=0;q.push(s),vis[s]=1;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=0;
for(int i:e[u]){
int v=eg[i].v,w=eg[i].w;
if(d[v]<=d[u]+w||!eg[i].f) continue;
d[v]=d[u]+w;if(!vis[v]) q.push(v),vis[v]=1;
}
}
return d[t]!=Inf;
}
int dfs(int u,int a){
if(!a||u==t) return a;
vis[u]=1;
int f,flow=0;
for(int &j=cur[u];j<(int)e[u].size();j++){
int i=e[u][j],v=eg[i].v,w=eg[i].w;
if(!vis[v]&&d[v]==d[u]+w&&(f=dfs(v,min(eg[i].f,a)))){
a-=f,flow+=f,eg[i].f-=f,eg[i^1].f+=f;
}
if(!a) break;
}
vis[u]=0;
return flow;
}
int solve(){
int res=0,ret=0;
while(spfa()){
for(int i=0;i<=n;i++) cur[i]=0;
int k=dfs(s,Inf);
res+=k*d[t],ret+=k;
}
// cerr<<res<<'\n';
return ret;
}
}
inline pii operator +(pii x,pii y){
return MP(x.fi+y.fi,add(x.se,y.se));
}
inline pii operator *(pii x,pii y){
return MP(x.fi*y.fi,1ll*x.se*y.se%mod);
}
int n;
string ch;
int L[N],ln[N][N],lt[N][N];
string s[N][N];
int len[N];
int lent[N][N];
pii h[N][N];
pii hh[N][N][N];
string t[N][N];
int p[N];
map<pii,bool> vis[N];
pii pw[N*N];
void dfs(int i,int u,int j,pii hsh){
if(len[i]==N-1) return ;
if(vis[u].count(hsh)) return ;
vis[u][hsh]=1;
if(u==L[i]){
p[u]=j;
string c="";
hsh=hsh*pw[j]+hh[i][u][j-1];
for(int x=1;x<=L[i];x++){
for(int o=0;o<p[x];o++) c+=s[i][x][o];
}
// if(i==1){
// cerr<<p[1]<<' '<<p[2]<<' '<<p[3]<<' '<<c<<'\n';
// }
// cout<<c<<' '<<hsh<<'\n';
t[i][++len[i]]=c;lent[i][len[i]]=c.length();
h[i][len[i]]=hsh;
return ;
}
for(int k=max(1ll,j-ln[i][u+1]);k<=min(lt[i][u],j+u-L[i]);k++){
pii nw=hsh*pw[k]+hh[i][u][k-1];
// if(i==5) cerr<<
p[u]=k,dfs(i,u+1,j-k,nw),p[u]=0;
if(len[i]==N-1) return ;
}
}
map<pii,int> id;
int tot;
signed main(){
// freopen("k.in","r",stdin);
// freopen("k.out","w",stdout);
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
pw[0]=MP(1,1);for(int i=1;i<N*N;i++) pw[i]=pw[i-1]*bas;
cin>>n;getline(cin,ch);
for(int i=1;i<=n;i++){
getline(cin,ch);
string c="";int m=ch.length();
for(int j=0;j<m;j++){
if(ch[j]==' ') s[i][++L[i]]=c,c="";
else c+=ch[j];
}
s[i][++L[i]]=c;
for(int j=L[i];j;j--){
ln[i][j]=ln[i][j+1]+(lt[i][j]=s[i][j].length());
}
for(int j=1;j<=L[i];j++){
for(int k=0;k<lt[i][j];k++){
hh[i][j][k]=hh[i][j][k-1]*bas+MP(s[i][j][k],s[i][j][k]);
}
}
}
// for(int i=1;i<=n;i++){
// cerr<<"-----------\n";
// for(int j=1;j<=L[i];j++) cerr<<s[i][j]<<'\n';
// }
for(int i=1;i<=n;i++){
for(int j=L[i];j<=ln[i][1];j++){
for(int k=1;k<=L[i];k++) vis[k].clear();
dfs(i,1,j,MP(0,0));
if(len[i]==N-1) break;
}
}
// for(int i=1;i<=n;i++){
// cerr<<"-----------\n";
// for(int j=1;j<=len[i];j++) cerr<<t[i][j]<<'\n';
// }
for(int i=1;i<=n;i++){
for(int j=1;j<=len[i];j++) if(!id.count(h[i][j])) id[h[i][j]]=++tot;
}
mf::init();
mf::n=n+tot+1;
mf::s=0,mf::t=n+tot+1;
for(int i=1;i<=n;i++) mf::add_edge(mf::s,i,1,0);
for(int i=1;i<=tot;i++) mf::add_edge(i+n,mf::t,1,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=len[i];j++){
int x=id[h[i][j]];
mf::add_edge(i,x+n,1,lent[i][j]);
}
}
int res=mf::solve();
if(res!=n) return cout<<"no solution\n",0;
for(int i=1;i<=n;i++){
for(int o:mf::e[i]) if(!mf::eg[o].f){
if(!mf::eg[o].v) continue;
int v=mf::eg[o].v-n;
for(int j=1;j<=len[i];j++) if(id[h[i][j]]==v){
cout<<t[i][j]<<'\n';break;
}
break;
}
}
return 0;
}
//86989
/*
5
a a a
aa a
aaa a a
aaaa a a
aaaaa a
*/
詳細信息
Test #1:
score: 100
Accepted
time: 7ms
memory: 91240kb
input:
5 automated teller machine active teller machine active trouble maker always telling misinformation American Teller Machinery
output:
autm atem atma atm ATM
result:
ok len=18
Test #2:
score: 0
Accepted
time: 19ms
memory: 90664kb
input:
5 Forest Conservation Committee Forum Fuming Corruption Collusion Federation Fulsome Cash Concealment Foundation Funky Crony Capitalism Facilitator Funny Cocky Cocky Funny
output:
FCCoF FCCFe FCCFo FCCFa FCCF
result:
ok len=24
Test #3:
score: 0
Accepted
time: 13ms
memory: 89472kb
input:
3 A AA AA A A A A
output:
no solution
result:
ok len=-1
Test #4:
score: 0
Accepted
time: 15ms
memory: 91024kb
input:
2 QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnmertyuiop Q W E R T Y U I O P A S D F G H J K L Z X C V B N M q w e r t y u i o p a s d f g h j k l z x c v b n m j k l z x c v b n m
output:
Q QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnmjklzxcvbnm
result:
ok len=63
Test #5:
score: 0
Accepted
time: 8ms
memory: 90716kb
input:
10 aaa aaa aaa aaa aaa aaa aab aaa aaa aaa aaa aaa aaa aab aaa aaa aaa aaa aab aab aaa aaa aaa aaa a a a a a a ab ab a a a a a a ab ab b a a a a a a aw a a a a a az az a a a a az a a a a a
output:
aaaaaaa aabaaaaa aaaaaaaaa aaabaaaa aaaaaa aaaaaaaa aabaaaaaa awaaaaa aazaaaa azaaaaa
result:
ok len=76
Test #6:
score: -100
Wrong Answer
time: 685ms
memory: 166600kb
input:
128 zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
output:
no solution
result:
wrong answer Jury has the answer but participant has not