oj.uz

답안 #1034963

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1034963 2024-07-26T00:53:31 Z ainta COVID tests (CEOI24_covid) C++17
70.45 / 100
 1851 ms 1048576 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], D2[1010];
int P1[1010], P2[1010];


void Go2(int b, int e);
void Go(int b, int e){
	if(b==e){
		answer[b]=1;
		return;
	}
	int N = e-b+1;
	if(P1[N]>0){
		int c = P1[N];
		if(test_range(b,b+c-1)){
			Go(b,b+c-1);
			Go2(b+c,e);
		}
		else{
			Go(b+c,e);
		}
	}	
	else{
		rng(i,b,e){
			if(test_range(i,i))answer[i]=1;
		}
	}
}


void Go2(int b, int e){
	if(b==e){
		if(test_range(b,b))answer[b]=1;
		return;
	}
	int N = e-b+1;
	if(P2[N]>8e8){
		if(test_range(b,e)){
			Go(b,e);
		}
		return;
	}
	if(P2[N]>0){
		int c = P2[N];
		Go2(b,b+c-1);
		Go2(b+c,e);
	}
	else if(P2[N]<0){
		int c = -P2[N];
		if(test_range(b,b+c-1)){
			Go(b,b+c-1);
			Go2(b+c,e);
		}
		else{
			Go2(b+c,e);
		}
	}
	else{
		rng(i,b,e){
			if(test_range(i,i))answer[i]=1;
		}
	}
}
int T;
std::vector<bool> find_positive() {
	answer.resize(N);
	mask.resize(N);
	rep(i,N)answer[i]=0;
	if(T==1){
		rep(i,N)answer[i] = test_range(i,i);
		return answer;
	}
	Go2(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() {
    scanf("%d %lf %d", &N, &P, &T);

	D[1] = 0;
	D2[1] = 1;

	rng(i,2,N){
		D2[i]=D[i]=i;
		P1[i]=P2[i]=i;
		rng(j,1,i-1){
			double p = (1-pow(1-P,j)) / (1-pow(1-P,i));
			double q = 1-p;
			double t2 = q * (1+D[i-j]) + p * (1 + D[j] +  D2[i-j]);
			double t3 = D2[j]+D2[i-j];
			double t4 = q * (1+D2[i-j]) + p * (1 + D[j] +  D2[i-j]);
			if(D[i] > t2){
				D[i] = t2;
				P1[i] = j;
			}
			if(D2[i] > t3){
				D2[i] = t3;
				P2[i] = j;
			}
			if(D2[i] > t4){
				D2[i] = t4;
				P2[i] = -j;
			}
		}
		double z = (1-pow(1-P,i))* D[i]+1;
		if(D2[i] > z){
			D2[i] = z;
			P2[i] = 1e9;
		}
	}
	/*printf("%f\n",D2[N]);
	return 0;*/

    // 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: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:174:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |     scanf("%d %lf %d", &N, &P, &T);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:233:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  233 |    scanf(" %c", &verdict);
      |    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 523 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 344 KB Output is correct
2 Correct 33 ms 344 KB Output is correct
3 Correct 37 ms 344 KB Output is correct
4 Correct 32 ms 344 KB Output is correct
5 Correct 35 ms 344 KB Output is correct
6 Correct 38 ms 344 KB Output is correct
7 Correct 26 ms 460 KB Output is correct
8 Correct 24 ms 464 KB Output is correct
9 Correct 32 ms 344 KB Output is correct
10 Correct 23 ms 344 KB Output is correct
11 Correct 23 ms 344 KB Output is correct
12 Correct 23 ms 344 KB Output is correct
13 Correct 24 ms 344 KB Output is correct
14 Correct 23 ms 344 KB Output is correct
15 Correct 23 ms 344 KB Output is correct
16 Correct 14 ms 344 KB Output is correct
17 Correct 18 ms 344 KB Output is correct

Subtask #2
60.450000003 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 344 KB Output is correct (P=0.001, F=15.1, Q=13.2) -> 90.00 points
2 Correct 172 ms 456 KB Output is correct (P=0.005256, F=51.1, Q=55.9) -> 65.42 points
3 Correct 277 ms 356 KB Output is correct (P=0.011546, F=94.9, Q=106.5) -> 60.45 points
4 Correct 557 ms 344 KB Output is correct (P=0.028545, F=191.5, Q=213.9) -> 61.31 points
5 Correct 724 ms 344 KB Output is correct (P=0.039856, F=246.3, Q=273.3) -> 62.57 points
6 Correct 1052 ms 344 KB Output is correct (P=0.068648, F=366.2, Q=398.8) -> 66.37 points
7 Correct 1360 ms 344 KB Output is correct (P=0.104571, F=490.3, Q=523.0) -> 71.05 points
8 Correct 1779 ms 344 KB Output is correct (P=0.158765, F=639.1, Q=664.1) -> 77.82 points
9 Correct 1851 ms 456 KB Output is correct (P=0.2, F=731.4, Q=750.5) -> 81.49 points