QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#358668#4632. Card SharkKevin5307WA 1ms5884kbC++201.7kb2024-03-19 22:17:542024-03-19 22:17:54

Judging History

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

  • [2024-03-19 22:17:54]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5884kb
  • [2024-03-19 22:17:54]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int fa[200200],deg[200200];
bool flag[200200];
int anc(int x)
{
	while(fa[x]!=x) x=fa[x]=fa[fa[x]];
	return x;
}
vector<pii> G[200200];
vector<int> ans;
void dfs(int x)
{
	if(!sz(G[x])) return ;
	int e=G[x].back().first;
	int y=G[x].back().second;
	G[x].pop_back();
	dfs(y);
	ans.pb(e);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=0;i<m;i++)
		fa[i]=i;
	for(int j=1;j<=n;j++)
	{
		map<int,int> Mp,Mp2;
		string s;
		cin>>s;
		for(int i=0;i<sz(s);i++)
			if(s[i]=='1')
				Mp[i%m]++;
			else
				Mp2[i%m]++;
		if(sz(Mp)!=1||Mp2[Mp.begin()->first])
			die("-1");
		int st=(Mp.begin()->first-q+m+1)%m;
		st=(m-st)%m;
		int nd=(st+sz(s))%m;
		fa[anc(st)]=anc(nd);
		deg[st]++;
		deg[nd]--;
		flag[st]=flag[nd]=1;
		G[st].pb(j,nd);
	}
	for(int i=0;i<m;i++)
		if(deg[i])
			die("-1");
	for(int i=0;i<m;i++)
		if(flag[i]&&anc(i)!=anc(0))
			die("-1");
	for(int i=0;i<m;i++)
		rsrt(G[i]);
	dfs(0);
	rev(ans);
	for(auto x:ans)
		cout<<x<<" ";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3560kb

input:

5 4 3
0100010
00100
001000100
0010
0100010

output:

2 1 3 5 4 

result:

ok single line: '2 1 3 5 4 '

Test #2:

score: 0
Accepted
time: 1ms
memory: 5644kb

input:

4 2 1
010
10101
010
10101

output:

2 1 4 3 

result:

ok single line: '2 1 4 3 '

Test #3:

score: 0
Accepted
time: 1ms
memory: 5640kb

input:

1 5 3
001000010000100

output:

1 

result:

ok single line: '1 '

Test #4:

score: 0
Accepted
time: 1ms
memory: 5884kb

input:

2 5 3
01000
00010

output:

-1

result:

ok single line: '-1'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

1 5 3
11111

output:

-1

result:

ok single line: '-1'

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 5592kb

input:

10 5 3
000010000100
0001000010000100001
000100
00010
00010000100
0010
00001000010000100001000010
00010
001
001000010

output:

6 2 1 9 7 3 10 4 5 

result:

wrong answer 1st lines differ - expected: '6 2 1 9 7 3 10 4 8 5', found: '6 2 1 9 7 3 10 4 5 '