QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#379114 | #8566. Can We Still Qualify For Semifinals? | ucup-team266# | AC ✓ | 3ms | 3888kb | C++23 | 3.5kb | 2024-04-06 16:14:42 | 2024-04-06 16:14:44 |
Judging History
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