QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#379462 | #8566. Can We Still Qualify For Semifinals? | ucup-team1447# | WA | 1ms | 5876kb | C++14 | 2.2kb | 2024-04-06 17:34:26 | 2024-04-06 17:34:28 |
Judging History
answer
// what is matter? never mind.
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define int long long
#define ull unsigned long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 500005
#define inf 0x3f3f3f3f
int n,p[maxn];
int e[15][15],f[15][15];
pii t[maxn];
int m;
int d[15];
bool solve(int s){
For(i,1,n) For(j,1,n) e[i][j]=f[i][j];
For(i,1,n)d[i]=0;
For(i,1,n) For(j,1,n) if(e[i][j]==1) ++d[i];
// For(i,1,n)cout<<d[i]<<" "; cout<<" d\n";
vi o;
For(i,2,n){
if(s>>(i-1)&1){
}else{
o.pb(i);
}
}
while(o.size()){
sort(o.begin(),o.end(),[&](int u,int v){
return d[u]<d[v];
});
int u=o.back();o.pop_back();
if(d[u]>d[1]) return 0;
int tmp=d[1]-d[u];
Rep(i,(int)o.size()-1,0){
int x=o[i];
if(e[x][u]==-1){
if(tmp) --tmp;
else ++d[x];
}
}
}
// cout<<"ok "<<s<<"\n";
return 1;
}
void work()
{
n=10;
For(i,1,n)For(j,1,n)e[i][j]=-1;
int k=read(); string s;cin>>s;
For(i,0,k-1){
int u=t[i].fi,v=t[i].se;
// cout<<"u,v "<<u<<" "<<v<<" "<<(s[i]&1)<<"\n";
e[u][v]=(s[i]&1);
e[v][u]=(!e[u][v]);
}
For(i,1,1)For(j,2,n) if(e[i][j]==-1) e[i][j]=1,e[j][i]=0;
For(i,1,n)For(j,1,n) f[i][j]=e[i][j];
// want 1 win.
For(i,1,n)d[i]=0;
For(i,1,n) For(j,1,n) if(e[i][j]==1) ++d[i];
For(s,0,(1<<n)-1)
if((s&1) && (__builtin_popcount(s))==4){
if(solve(s)){
puts("YES");
return;
}
}
puts("NO");
}
signed main()
{
n=10;
For(i,1,10)p[i]=i;
For(i,1,9){
For(j,1,5) t[m++]=mkp(p[j],p[n+1-j]);
rotate(p+2,p+n,p+n+1);
}
int T=read();
while(T--)work();
return 0;
}
/*
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5608kb
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: 1ms
memory: 5584kb
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: 5624kb
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: 1ms
memory: 5620kb
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: 5876kb
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: 1ms
memory: 5612kb
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: 5584kb
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: 3764kb
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: -100
Wrong Answer
time: 0ms
memory: 5584kb
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 NO YES NO
result:
wrong answer expected YES, found NO [8th token]