oj.uz

답안 #1026558

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1026558 2024-07-18T07:57:30 Z 정희우(#10948) COVID tests (CEOI24_covid) C++17
88.2 / 100
 1495 ms 600 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<random>
#include<ctime>

using namespace std;
using lint = long long;
using intp = pair<int,int>;
using vint = vector<int>;

const int MAX_N=1010;

int n,q;
double p;
int sf[MAX_N];
char ask[MAX_N];
char ans[MAX_N];
int chunk;

int askq()
{
    char c;
    cout << "Q " << ask << endl;
    cin >> c;
    return (c=='P');
}

void calc(int s)
{
    if(s>=n)
        return;
    vint v;
    for(int i=0;i<chunk && s+i<n;i++)
        if(ans[sf[s+i]]=='0')
            v.push_back(sf[s+i]);
    if(v.empty())
    {
        calc(s+chunk);
        return;
    }
    for(auto x : v)ask[x]='1';
    int a=askq();
    for(auto x : v)ask[x]='0';
    if(!a)
    {
        calc(s+chunk);
        return;
    }
    int lb=0,ub=v.size()-1;
    while(lb<ub)
    {
        int m=(lb+ub)/2;
        for(int i=lb;i<=m;i++)ask[v[i]]='1';
        int a=askq();
        for(int i=lb;i<=m;i++)ask[v[i]]='0';
        if(a)ub=m;
        else lb=m+1;
    }
    ans[v[lb]]='1';
    calc(s+lb+1);
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> p >> q;
    fill(ask,ask+n,'0');
    fill(ans,ans+n,'0');
    if(q==1)
    {
        for(int i=0;i<n;i++)
        {
            ask[i]='1';
            ans[i]='0'+askq();
            ask[i]='0';
        }
        char c;
        cout << "A " << ans << endl;
        cin >> c;
        return 0;
    }
    srand(time(NULL));
    for(int i=0;i<n;i++)
        sf[i]=i;
    for(int i=0;i<n;i++)
        swap(sf[i],sf[i+(rand()%(n-i))]);
    chunk=1/p*0.5;
    while(q--)
    {
        fill(ans,ans+n,'0');
        calc(0);
        char c;
        cout << "A " << ans << endl;
        cin >> c;
    }
    return 0;
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 4 ms 344 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 8 ms 344 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 5 ms 344 KB Output is correct
16 Correct 7 ms 344 KB Output is correct
17 Correct 6 ms 344 KB Output is correct

Subtask #2
78.200000001 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 344 KB Output is correct (P=0.001, F=15.1, Q=10.9) -> 90.00 points
2 Correct 81 ms 448 KB Output is correct (P=0.005256, F=51.1, Q=47.5) -> 90.00 points
3 Correct 184 ms 444 KB Output is correct (P=0.011546, F=94.9, Q=92.6) -> 90.00 points
4 Correct 393 ms 344 KB Output is correct (P=0.028545, F=191.5, Q=191.6) -> 89.81 points
5 Correct 506 ms 344 KB Output is correct (P=0.039856, F=246.3, Q=251.1) -> 83.49 points
6 Correct 616 ms 600 KB Output is correct (P=0.068648, F=366.2, Q=375.0) -> 82.11 points
7 Correct 839 ms 464 KB Output is correct (P=0.104571, F=490.3, Q=503.0) -> 81.55 points
8 Correct 1251 ms 464 KB Output is correct (P=0.158765, F=639.1, Q=663.2) -> 78.20 points
9 Correct 1495 ms 592 KB Output is correct (P=0.2, F=731.4, Q=757.2) -> 78.87 points