oj.uz

답안 #1034339

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1034339 2024-07-25T12:29:14 Z ainta COVID tests (CEOI24_covid) C++17
56.34 / 100
 2025 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;

#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;

#include <cassert>
#include <cstdio>
#include <string>
#include <vector>

/// You may use:

// The number of students
int N;

// The probability any given student is positive
double P;

int DEBUG = 0;

// This function performs a test on a subset of samples.
// Its argument is a vector of Booleans of length N,
// where the i-th element is true if the i-th sample should be added to the mix.
// It returns true if (and only if) at least one of the samples in the mix is positive.

int Z[1010];

int cnt=0;

bool test_students(std::vector<bool> mask) {
	cnt++;
    assert(mask.size() == (size_t)N);

    std::string mask_str(N, ' ');
    for (int i = 0; i < N; i++)
        mask_str[i] = mask[i] ? '1' : '0';

	if(!DEBUG){
	    printf("Q %s\n", mask_str.c_str());
    	fflush(stdout);
		char answer;
		scanf(" %c", &answer);
		return answer == 'P';
	}
	int ss=0;
	rep(i,N){
		if(mask[i]) ss|=Z[i];
	}
	return ss;
}

std::vector<bool>answer, mask;
bool test_range(int b, int e){
	rep(i,N)mask[i]=0;
	rng(i,b,e)mask[i]=1;
	return test_students(mask);
}

/// You should implement:

// This function will be called once for each test instance.
// It should use test_students to determine which samples are positive.
// It must return a vector of Booleans of length N,
// where the i-th element is true if and only if the i-th sample is positive.

double D[1010];
int Path[1010];

void Go(int b, int e){
	if(b==e){
		answer[b]=1;
		return;
	}
	int N = e-b+1;
	if(Path[N]){
		int c = Path[N];
		if(test_range(b,b+c-1)){
			Go(b,b+c-1);
			if(test_range(b+c,e)) Go(b+c,e);
		}
		else{
			Go(b+c,e);
		}
	}
	else{
		rng(i,b,e){
			if(test_range(i,i))answer[i]=1;
		}
	}
}
std::vector<bool> find_positive() {
	answer.resize(N);
	mask.resize(N);
	rep(i,N)answer[i]=0;
	int s = 0;
	if(test_range(0,N-1)){
		Go(0,N-1);
	}
    return answer;
}



ll rand_int(ll l, ll r) { //[l, r]
	#ifdef LOCAL
	static mt19937_64 gen;
	#else
    static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
    #endif
    return uniform_int_distribution<ll>(l, r)(gen);
}
int main() {
    int T;
    scanf("%d %lf %d", &N, &P, &T);

	rng(i,2,N){
		D[i]=i;
		Path[i] = 0;
		rng(j,1,i-1){
			double p = (1-pow(1-P,j)) / (1-pow(1-P,i));
			double q = 1-p;
			double s = q * (1+D[i-j]) + p * (2 + D[j] +  (1-pow(1-P,i-j))  * D[i-j] );
			if(D[i]>s){
				Path[i] = j;
				D[i]=s;
			}
		}
		//printf("%d %f\n",i,D[i]);
	}

    // You may perform any extra initialization here.

    for (int i = 0; i < T; i++) {
		if(DEBUG){
			rep(j,N){
				if(rand_int(0,999) < P*1000){
					Z[j]=1;
				}
				else Z[j]=0;
			}
		}
        std::vector<bool> answer = find_positive();
        assert(answer.size() == (size_t)N);

        std::string answer_str(N, ' ');
        for (int j = 0; j < N; j++)
            answer_str[j] = answer[j] ? '1' : '0';

		if(!DEBUG){
			printf("A %s\n", answer_str.c_str());
			fflush(stdout);

			char verdict;
			scanf(" %c", &verdict);
			if (verdict == 'W')
				exit(0);
		}
    }

	if(DEBUG)printf("%f\n",(double)cnt/T);
    return 0;
}

Compilation message

Main.cpp: In function 'bool test_students(std::vector<bool>)':
Main.cpp:57:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   57 |     for (int i = 0; i < N; i++)
      |     ^~~
Main.cpp:60:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   60 |  if(!DEBUG){
      |  ^~
Main.cpp: In function 'std::vector<bool> find_positive()':
Main.cpp:117:6: warning: unused variable 's' [-Wunused-variable]
  117 |  int s = 0;
      |      ^
Main.cpp: In function 'bool test_students(std::vector<bool>)':
Main.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   scanf(" %c", &answer);
      |   ~~~~~^~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:136:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |     scanf("%d %lf %d", &N, &P, &T);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:176:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |    scanf(" %c", &verdict);
      |    ~~~~~^~~~~~~~~~~~~~~~~

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 47 ms 344 KB Output is correct
2 Correct 47 ms 344 KB Output is correct
3 Correct 45 ms 340 KB Output is correct
4 Correct 43 ms 344 KB Output is correct
5 Correct 45 ms 428 KB Output is correct
6 Correct 56 ms 428 KB Output is correct
7 Correct 34 ms 344 KB Output is correct
8 Correct 29 ms 344 KB Output is correct
9 Correct 40 ms 344 KB Output is correct
10 Correct 28 ms 344 KB Output is correct
11 Correct 33 ms 452 KB Output is correct
12 Correct 33 ms 452 KB Output is correct
13 Correct 31 ms 444 KB Output is correct
14 Correct 33 ms 344 KB Output is correct
15 Correct 31 ms 344 KB Output is correct
16 Correct 19 ms 604 KB Output is correct
17 Correct 16 ms 344 KB Output is correct

Subtask #2
46.340000001 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 444 KB Output is correct (P=0.001, F=15.1, Q=13.2) -> 90.00 points
2 Correct 166 ms 344 KB Output is correct (P=0.005256, F=51.1, Q=58.5) -> 56.99 points
3 Correct 319 ms 344 KB Output is correct (P=0.011546, F=94.9, Q=113.7) -> 50.21 points
4 Correct 576 ms 344 KB Output is correct (P=0.028545, F=191.5, Q=232.5) -> 48.48 points
5 Correct 721 ms 344 KB Output is correct (P=0.039856, F=246.3, Q=300.5) -> 47.87 points
6 Correct 1042 ms 344 KB Output is correct (P=0.068648, F=366.2, Q=445.5) -> 48.23 points
7 Correct 1408 ms 344 KB Output is correct (P=0.104571, F=490.3, Q=595.4) -> 48.45 points
8 Correct 1920 ms 344 KB Output is correct (P=0.158765, F=639.1, Q=777.7) -> 48.19 points
9 Correct 2025 ms 344 KB Output is correct (P=0.2, F=731.4, Q=903.7) -> 46.34 points