QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #471114 | #8566. Can We Still Qualify For Semifinals? | ucup-team2307# | AC ✓ | 1201ms | 3964kb | C++20 | 2.1kb | 2024-07-10 18:12:36 | 2024-07-10 18:12:38 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
typedef long long ll;
#define int ll
using namespace std;
string s = string{"1 vs 10 1 vs 9 1 vs 8 1 vs 7 1 vs 6 1 vs 5 1 vs 4 1 vs 3 1 vs 2 "}+
"2 vs 9 10 vs 8 9 vs 7 8 vs 6 7 vs 5 6 vs 4 5 vs 3 4 vs 2 3 vs 10 "+
"3 vs 8 2 vs 7 10 vs 6 9 vs 5 8 vs 4 7 vs 3 6 vs 2 5 vs 10 4 vs 9 "+
"4 vs 7 3 vs 6 2 vs 5 10 vs 4 9 vs 3 8 vs 2 7 vs 10 6 vs 9 5 vs 8 "+
"5 vs 6 4 vs 5 3 vs 4 2 vs 3 10 vs 2 9 vs 10 8 vs 9 7 vs 8 6 vs 7 ";
vector<pair<int, int> > ord;
void read()
{
vector<pair<int, int> > t;
stringstream ss;
ss<<s;
for (int i=0; i<45; i++)
{
int x, y;
string q;
ss>>x>>q>>y;
x--, y--;
t.pb({x, y});
}
for (int i=0; i<9; i++)
for (int j=i; j<45; j+=9)
ord.pb(t[j]);
}
void solve(double T)
{
int k;
cin>>k;
string s;
cin>>s;
vector<pair<int, int> > lt;
vector<int> sc(10);
for (int i=0; i<k; i++)
{
if (s[i] == '1')
sc[ord[i].fi]++;
else
sc[ord[i].se]++;
}
for (int i=k; i<45; i++)
if (ord[i].fi == 0)
sc[0]++;
else
lt.pb(ord[i]);
auto sc0 = sc;
while (true)
{
sc = sc0;
random_shuffle(lt.begin(), lt.end());
for (auto [x, y] : lt)
if (sc[x] > sc[0])
sc[x]++;
else if (sc[y] > sc[0])
sc[y]++;
else if (sc[x] - rand()%2 < sc[y])
sc[x]++;
else
sc[y]++;
int cnt =0;
for (int i=1; i<10; i++)
if (sc[i] > sc[0])
cnt++;
if (cnt <= 3)
{
cout<<"YES\n";
return;
}
if (clock()*1.0/CLOCKS_PER_SEC > T)
break;
}
cout<<"NO\n";
return;
}
main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
srand(time(0));
read();
int t;
cin>>t;
for (int i=1; i<=t; i++)
solve(i*1.5/t);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 972ms
memory: 3644kb
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: 3928kb
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: 954ms
memory: 3640kb
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: 1092ms
memory: 3964kb
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: 1201ms
memory: 3636kb
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: 1161ms
memory: 3764kb
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: 1124ms
memory: 3960kb
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: 1100ms
memory: 3644kb
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: 818ms
memory: 3732kb
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