QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#471114#8566. Can We Still Qualify For Semifinals?ucup-team2307#AC ✓1201ms3964kbC++202.1kb2024-07-10 18:12:362024-07-10 18:12:38

Judging History

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

  • [2024-07-10 18:12:38]
  • 评测
  • 测评结果:AC
  • 用时:1201ms
  • 内存:3964kb
  • [2024-07-10 18:12:36]
  • 提交

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);
}

详细

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