QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#753397#9558. The Devilucup-team3931#WA 685ms166600kbC++144.5kb2024-11-16 12:43:552024-11-16 12:44:04

Judging History

你现在查看的是最新测评结果

  • [2024-11-16 12:44:04]
  • 评测
  • 测评结果:WA
  • 用时:685ms
  • 内存:166600kb
  • [2024-11-16 12:43:55]
  • 提交

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