QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #378728 | #8566. Can We Still Qualify For Semifinals? | ucup-team3396# | AC ✓ | 1ms | 3804kb | C++14 | 3.7kb | 2024-04-06 14:23:12 | 2024-04-06 14:23:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int head[20001];int to[20001];
int nxt[20001];int cur[20001];
long long flow[20001];
int dep[10001];
bool vis[10001];
int s,t;
int tot=2;
void add(int s,int t,int w){
nxt[tot]=head[s];flow[tot]=w;
to[tot]=t;head[s]=tot;tot++;
return ;
}
void init(){
for(int i=1;i<=t;i++)head[i]=0;
tot=2;
return ;
}
bool bfs(){
for(int i=1;i<=t;i++)dep[i]=vis[i]=0,cur[i]=head[i];
queue<int> d;d.push(s);dep[s]=0;bool ok=0;vis[s]=1;
while(!d.empty()){
int g=d.front();d.pop();
if(g==t)ok=1;
for(int i=head[g];i;i=nxt[i]){
if(flow[i]!=0 and !vis[to[i]])dep[to[i]]=dep[g]+1,vis[to[i]]=1,d.push(to[i]);
}
}
return ok;
}
long long dfs(int g,long long pre){
if(g==t)return pre;
long long used=0;
for(int i=cur[g];i;i=nxt[i]){
cur[g]=i;
if(dep[to[i]]==dep[g]+1 and flow[i]!=0){
long long res=dfs(to[i],min(flow[i],pre-used));
used+=res;
flow[i]-=res;
flow[i^1]+=res;
}
if(used==pre)return pre;
}
return used;
}
int solve(){
int ans=0;
while(bfs()){
ans+=dfs(s,INT_MAX);
}
return ans;
}
int num[11];
pair<int,int> w[101];
int ttt=0;
int z;
bool vst[101];
signed main(){
vector<int> o;
//for(int i=1;i<=10;i++)o.push_back(i);
for(int i=1;i<=9;i++){
o.clear();
o.push_back(1);
for(int j=10-i+2;j<=10;j++)o.push_back(j);
for(int j=2;j<=10-i+1;j++)o.push_back(j);
for(int j=0;j<5;j++){
ttt++;
w[ttt]={o[j],o[9-j]};
}
}
int T;cin>>T;
while(T--){
int len;cin>>len;
string S;cin>>S;
S=" "+S;
for(int i=1;i<=10;i++)num[i]=0;
z=S.size()-1;
for(int i=1;i<S.size();i++){
if(S[i]=='1')num[w[i].first]++;
else num[w[i].second]++;
}
for(int i=z+1;i<=45;i++){
if(w[i].first==1 or w[i].second==1)num[1]++;
}
bool ans=0;
for(int i=2;i<=10;i++){
for(int j=i+1;j<=10;j++){
for(int k=j+1;k<=10;k++){
init();
bool flg=0;
for(int p=2;p<=10;p++){
if(p!=i and p!=j and p!=k and num[p]>num[1]){
flg=1;break;
}
}
if(flg)continue;
s=56,t=57;
int ooo=0;
for(int p=z+1;p<=45;p++){
if(w[p].first==1 or w[p].first==i or w[p].first==j or w[p].first==k or w[p].second==1 or w[p].second==i or w[p].second==j or w[p].second==k)continue;
ooo++;
add(s,p,1);add(p,s,0);
}
for(int p=2;p<=10;p++){
if(p==i or p==j or p==k)continue;
add(45+p,t,num[1]-num[p]);
add(t,45+p,0);
}
for(int p=z+1;p<=45;p++){
if(w[p].first==1 or w[p].first==i or w[p].first==j or w[p].first==k or w[p].second==1 or w[p].second==i or w[p].second==j or w[p].second==k)continue;
add(p,45+w[p].first,1);add(45+w[p].first,p,0);
add(p,45+w[p].second,1);add(45+w[p].second,p,0);
}
int qq=solve();
if(qq==ooo){
ans=1;break;
}
}
if(ans)break;
}
if(ans)break;
}
if(ans)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
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: 0ms
memory: 3628kb
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: 0ms
memory: 3572kb
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: 0ms
memory: 3640kb
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: 0ms
memory: 3632kb
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: 0ms
memory: 3632kb
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: 0ms
memory: 3628kb
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: 3804kb
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: 0ms
memory: 3804kb
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: 0ms
memory: 3804kb
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