QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#379114#8566. Can We Still Qualify For Semifinals?ucup-team266#AC ✓3ms3888kbC++233.5kb2024-04-06 16:14:422024-04-06 16:14:44

Judging History

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

  • [2024-04-06 16:14:44]
  • 评测
  • 测评结果:AC
  • 用时:3ms
  • 内存:3888kb
  • [2024-04-06 16:14:42]
  • 提交

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);}
class MaximumFlow
{
	private:
		struct edge
		{
			int u,v,capa;
		}E[10010];
		edge make_edge(int u,int v,int capa)
		{
			edge e;
			e.u=u;
			e.v=v;
			e.capa=capa;
			return e;
		}
		vector<int> G[1010];
		int p;
		bool inque[1010];
		int dep[1010];
		bool bfs(int s,int t)
		{
			for(int i=0;i<1010;i++)
				dep[i]=inf;
			memset(inque,0,sizeof(inque));
			dep[s]=0;
			inque[s]=1;
			queue<int> q;
			q.push(s);
			while(!q.empty())
			{
				int x=q.front();
				q.pop();
				inque[x]=0;
				for(int e:G[x])
				{
					int v=E[e].v;
					if(dep[v]>dep[x]+1&&E[e].capa)
					{
						dep[v]=dep[x]+1;
						if(!inque[v])
						{
							q.push(v);
							inque[v]=1;
						}
					}
				}
			}
			return (dep[t]!=inf);
		}
		int dfs(int u,int t,int aug)
		{
			int naug=0;
			if(u==t)
				return aug;
			for(int e:G[u])
			{
				int v=E[e].v;
				if(E[e].capa&&dep[v]==dep[u]+1)
				{
					if((naug=dfs(v,t,min(aug,E[e].capa))))
					{
						E[e].capa-=naug;
						E[e^1].capa+=naug;
						return naug;
					}
				}
			}
			return 0;
		}
	public:
		void clear()
		{
			p=0;
			for(int i=0;i<1010;i++)
				G[i].clear();
		}
		MaximumFlow()
		{
			clear();
		}
		void addEdge(int u,int v,int capa)
		{
			G[u].pb(p);
			E[p++]=make_edge(u,v,capa);
			G[v].pb(p);
			E[p++]=make_edge(v,u,0);
		}
		int dinic(int s,int t)
		{
			int flow;
			int maxflow=0;
			while(bfs(s,t))
				while((flow=dfs(s,t,inf)))
					maxflow+=flow;
			return maxflow;
		}
};
MaximumFlow mf;
vector<int> a,b;
int cnt[15];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	for(int i=11;i>=3;i--)
	{
		vector<int> tmp;
		tmp.pb(1);
		for(int j=i;j<=10;j++)
			tmp.pb(j);
		for(int j=2;j<i;j++)
			tmp.pb(j);
		for(int x=0;x<5;x++)
			a.pb(tmp[x]);
		for(int x=0;x<5;x++)
			b.pb(tmp[9-x]);
	}
	int t;
	cin>>t;
	while(t--)
	{
		int k;
		cin>>k;
		string s;
		cin>>s;
		memset(cnt,0,sizeof(cnt));
		for(int i=0;i<k;i++)
			if(s[i]=='1')
				cnt[a[i]]++;
			else
				cnt[b[i]]++;
		int tot=0;
		for(int i=k;i<45;i++)
			if(a[i]==1||b[i]==1)
				cnt[1]++;
		bool result=0;
		for(int aa=2;aa<=10;aa++)
			for(int bb=aa+1;bb<=10;bb++)
				for(int cc=bb+1;cc<=10;cc++)
				{
					tot=0;
					mf.clear();
					for(int i=k;i<45;i++)
						if(a[i]>1&&b[i]>1)
						{
							mf.addEdge(100,i,1);
							tot++;
							mf.addEdge(i,45+a[i],1);
							mf.addEdge(i,45+b[i],1);
						}
					bool ok=1;
					for(int i=1;i<=10;i++)
						if(i==aa||i==bb||i==cc)
							mf.addEdge(45+i,101,1000);
						else
						{
							if(cnt[i]>cnt[1])
								ok=0;
							else
								mf.addEdge(45+i,101,cnt[1]-cnt[i]);
						}
					if(ok&&mf.dinic(100,101)==tot)
						result=1;
				}
		if(result)
			puts("YES");
		else
			puts("NO");
	}
	return 0;
}

详细

Test #1:

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

input:

3
3
111
25
1000010101111111111010100
35
01111011110111101111011110111101111

output:

YES
YES
NO

result:

ok 3 token(s): yes count is 2, no count is 1

Test #2:

score: 0
Accepted
time: 2ms
memory: 3688kb

input:

10
16
0110000001010100
17
01111000110110101
15
001100010101111
16
0010101010011100
19
0000000100010110100
16
0011101010011100
18
011110010001100000
18
000110101001100011
20
01100010000100100100
15
001000111001101

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES

result:

ok 10 token(s): yes count is 10, no count is 0

Test #3:

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

input:

10
37
0110000001010100011101001011100110001
39
000100111101101001100101101000000000100
35
00111000100111100101011010111100100
33
010000010001110010110001101110001
30
000100010100000010010110101010
31
0000101000011010101001010000000
44
00001000000111101011010110000101100011000100
42
01111011110001001...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO

result:

ok 10 token(s): yes count is 0, no count is 10

Test #4:

score: 0
Accepted
time: 2ms
memory: 3596kb

input:

10
23
01100000010101000111010
38
01111001100011000101011110101001101001
27
010000000001001001110001001
26
01101001110011101101000110
8
00001000
22
0110100110001110110001
9
000100010
24
000000100101101010100100
6
011000
29
01101010100101000000000000100

output:

YES
NO
NO
NO
YES
YES
YES
YES
YES
NO

result:

ok 10 token(s): yes count is 6, no count is 4

Test #5:

score: 0
Accepted
time: 2ms
memory: 3888kb

input:

10
30
011000000101010001110100101110
29
01001010010011101110010110010
28
0110000000001000101101001001
23
01101001110011101101000
23
01000001000111001011000
24
011110001000010001010000
23
01001011010101001000011
30
000110011001010010000000000010
24
000110111001110011000011
28
000110001000011011110110...

output:

NO
NO
NO
YES
YES
YES
YES
NO
YES
NO

result:

ok 10 token(s): yes count is 5, no count is 5

Test #6:

score: 0
Accepted
time: 3ms
memory: 3684kb

input:

10
21
011000000101010001110
21
000110110101001010010
22
0111101101001100101101
24
000000001000101011000101
21
011010011100111011010
20
00110000010001101010
21
010010111100010000100
24
010100000100011010110010
23
00001010000110101010010
25
0000000000001000001101110

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES

result:

ok 10 token(s): yes count is 10, no count is 0

Test #7:

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

input:

10
26
01100000010101000111010010
26
01101010010100100111011100
26
00110010110100000000010010
27
011100010101110010110101101
30
010100011000001000110101001100
30
011110001000010001010000001001
28
0101100101000010100001101010
26
00101000000000000100000110
28
0110101101010000111000110001
27
00011011110...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO

result:

ok 10 token(s): yes count is 0, no count is 10

Test #8:

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

input:

10
25
0010100010011010111001111
26
01001010100010101010001010
26
01111001110000100111011110
26
10001000100110101110011110
26
10101010100110101110011110
27
110100010101010011010111001
27
101010101001101011100111101
31
1000010001010100110001011011110
37
1000101111000100110000011000000100101
40
1000101...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO

result:

ok 10 token(s): yes count is 0, no count is 10

Test #9:

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

input:

10
26
00001010000000000000000000
26
00000010000000000000000000
26
01101010100010101011011110
26
00011011110111101111011110
27
001100110101011001110111101
27
000110111101111011110111101
28
0110001001000010011101111011
29
01000000010001101000011110111
29
01000000010000101101011110111
30
01000011110111...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
NO

result:

ok 10 token(s): yes count is 9, no count is 1

Test #10:

score: 0
Accepted
time: 2ms
memory: 3636kb

input:

10
1
0
2
00
10
0001101110
14
00101010000011
20
00000010010100101010
25
0000000101000100100001111
35
01110011010000101010000010010000100
40
0000100110001110101100001001000110000001
44
01011010110010101110011000010001010011100011
45
010010001001010011110111101011011000000100001

output:

YES
YES
YES
YES
YES
YES
NO
NO
NO
NO

result:

ok 10 token(s): yes count is 6, no count is 4

Extra Test:

score: 0
Extra Test Passed