oj.uz

답안 #1095536

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1095536 2024-10-02T14:07:27 Z razivo COVID tests (CEOI24_covid) C++14
0 / 100
 7000 ms 592 KB 
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include <math.h>
using namespace std;
void answer(vector<bool> &res) {
    cout<<"A ";
    for (int i = 0; i < res.size(); ++i) {
        if(res[i]) cout<<"1";
        else cout<<"0";
    }
    cout<<endl;
    string c; cin>>c;
    if(c=="W") exit(0);
}
bool test(vector<int> &i,int n) {
    cin.tie(0);
    cout<<"Q ";
    vector<bool> t(n,false);
    for(auto u:i) {
        t[u]=true;
    }
    for(auto u:t) {
        if(u) cout<<1;
        else cout<<0;
    }
    cout<<endl;
    string c; cin>>c;
    return c=="P";
}
void check(vector<int> &n, vector<bool> &res,priority_queue<int> &free,vector<int> &k,int N) {
    if(n.size()==0) return;
    if(n.size()==1) {
        res[n[0]]=true;
        return;
    }
    vector<int> toTest(k[n.size()]);
    for (int i = 0; i < k[n.size()]; ++i) {
        toTest[i]=n[i];
    }
    if(test(toTest,N)) {
        check(toTest,res,free,k,N);
        for (int i = k[n.size()]; i < n.size(); ++i) {
            free.push(n[i]);
        }
    }else {
        vector<int> u;
        for (int i = k[n.size()]; i < n.size(); ++i) {
            u.push_back(n[i]);
        }
        for (int i = 0; i < k[n.size()]; ++i) {
            res[i]=false;
        }
        check(u,res,free,k,N);
    }

}
int main()
{
    int N,T;
    double p;
    cin>>N>>p>>T;
    int background = -1/log2(1-p);
    vector<int> k(N);
    for (int i = 0; i < N; ++i) {
        double d =(log2(1-(1-pow(1-p,i))/2)/log2(1-p));
        k[i] = d;
        if(k[i]==0)k[i]=1;
    }
    for (int mi = 0; mi < T; ++mi) {
        vector<bool> res(N);
        priority_queue<int> free;
        for (int i= 0; i < N; ++i) {
            free.push(i);
        }
        while(!free.empty()) {
            vector<int> o;
            for (int i = 0; i < background; ++i) {
                if(!free.empty()) {
                    o.push_back(free.top()); free.pop();
                }
            }
            if(test(o,N)) {
                check(o,res,free,k,N);
            }else {
                for (int i :o) {
                    res[i]=false;
                }
            }
        }
        answer(res);
    }
}

Compilation message

Main.cpp: In function 'void answer(std::vector<bool>&)':
Main.cpp:9:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int i = 0; i < res.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
Main.cpp: In function 'void check(std::vector<int>&, std::vector<bool>&, std::priority_queue<int>&, std::vector<int>&, int)':
Main.cpp:44:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int i = k[n.size()]; i < n.size(); ++i) {
      |                                   ~~^~~~~~~~~~
Main.cpp:49:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int i = k[n.size()]; i < n.size(); ++i) {
      |                                   ~~^~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 7012 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 150 ms 592 KB Output is correct (P=0.001, F=15.1, Q=11.1) -> 90.00 points
2 Correct 648 ms 344 KB Output is correct (P=0.005256, F=51.1, Q=47.3) -> 90.00 points
3 Correct 1197 ms 344 KB Output is correct (P=0.011546, F=94.9, Q=92.2) -> 90.00 points
4 Correct 2298 ms 344 KB Output is correct (P=0.028545, F=191.5, Q=190.9) -> 90.00 points
5 Correct 2995 ms 344 KB Output is correct (P=0.039856, F=246.3, Q=250.1) -> 84.77 points
6 Correct 4466 ms 344 KB Output is correct (P=0.068648, F=366.2, Q=372.5) -> 84.21 points
7 Correct 5976 ms 344 KB Output is correct (P=0.104571, F=490.3, Q=498.1) -> 84.62 points
8 Execution timed out 7028 ms 344 KB Time limit exceeded
9 Halted 0 ms 0 KB -