QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#504785 | #9162. COVID tests | kwongweng# | 0 | 4024ms | 3972kb | C++17 | 3.3kb | 2024-08-04 15:57:56 | 2024-08-04 15:57:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef vector<vector<ll>> vll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define ms memset
#define fi first
#define se second
ll MOD = 998244353;
ll power(ll base, ll n){
base %= MOD;
if (n==0) return 1;
ll halfn = power(base,n/2);
if (n%2==0) return (halfn*halfn)%MOD;
return (((halfn*halfn)%MOD)*base)%MOD;
}
ll inverse(ll n){
return power(n,MOD-2);
}
ll C[3001][3001];
ll binom(int n, int k){
if (C[n][k]!=-1) return C[n][k];
if (n<k) return C[n][k] = 0;
if (k==0) return C[n][k] = 1;
return C[n][k] = (binom(n-1,k)+binom(n-1,k-1)) % MOD;
}
vll mul(vll A, vll B){
int n = A.size();
int m = B[0].size();
int p = B.size();
vll C; C.resize(n, vector<ll>(m,0LL));
FOR(i,0,n){
FOR(j,0,m){
FOR(k,0,p){
C[i][j] += (A[i][k]*B[k][j]) % MOD;
C[i][j] %= MOD;
}
}
}
return C;
}
vll exp(vll base, ll n){
int len = base.size();
vll ans; ans.resize(len,vector<ll>(len,0LL));
FOR(i,0,len) ans[i][i]=1;
if (n==0) return ans;
if (n==1) return base;
ans = mul(exp(base,n/2),exp(base,n/2));
if (n % 2 == 1) ans = mul(ans,base);
return ans;
}
/*
bipartite -> Alice wins
*/
const int N = 1000;
vi p(N), sz(N);
set<int> par;
int get(int a){
if (p[a]==a) return a;
return p[a]=get(p[a]);
}
void Union(int a, int b){
int c = get(a), d = get(b);
if (sz[c]<sz[d]) swap(c,d);
sz[c]+=sz[d];
p[d]=c; par.erase(d);
}
ll INF = 1e9;
ll f(ll n){
return ((n*(n+1))/2) % MOD;
}
int n;
vi val(N);
bool qry(){
cout<<"Q "; FOR(i,0,n) cout<<val[i];
cout<<endl;
char ans; cin>>ans;
return (ans=='N');
}
void print(){
cout<<"A "; FOR(i,0,n) cout<<1-val[i];
cout<<endl;
}
void find_positive(int L, int R){
if (L>R) return;
FOR(i,L,R+1){
val[i]=1;
}
if (qry()) return;
int l = L-1, r = R;
while (r-l>1){
int mid = (l+r)/2;
FOR(i,l+1,mid+1) val[i] = 1;
FOR(i,mid+1,r+1) val[i] = 0;
if (qry()) l=mid;
else r=mid;
}
FOR(i,L,r) val[i]=1;
val[r] = 0;
if (r==R) return;
find_positive(r+1,R);
}
void solve(){
double p; int t; cin>>n>>p>>t;
int v = floor(n*p);
while (t--){
FOR(i,0,n) val[i]=0;
if (p>=0.2){
FOR(i,0,n){
val[i]=1;
if (!qry()){
val[i]=0;
}
}
print();
char verdict; cin>>verdict;
if (verdict=='W') break;
continue;
}
FOR(i,0,v) find_positive(i*(n/v), (i+1)*(n/v)-1);
find_positive(v*(n/v),n-1);
print();
char verdict; cin>>verdict;
if (verdict=='W') break;
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int TC = 1; //cin>>TC;
while (TC--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 10
Accepted
time: 27ms
memory: 3676kb
input:
1000 0.789673 1 P N P P P P P P N P P N P N P P P P P N P P P P P P N P P P P P P P P P P P P P P P P P P N N N P P P P N P P P P N N P P P N P P P P N P P P P P N N P N P P P P P N P P P P P P P P P P P P P P P P P P N N P N P P P P P P P P N P N P P P N N P P P P P P P P P P P P P P P P P P P P N ...
output:
Q 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 1.0 translate:success
Test #2:
score: 10
Accepted
time: 24ms
memory: 3924kb
input:
1000 0.686378 1 N P N N N P N N P N P P N N P P P P N P P P N P P P N N P N P P P N N N P N P P P N P P P P P P N N P P P N P P P P P P P P P P P P P P P P P P N N P P N N N P P N P N P P P P P N P N N P P P N P N N P N P P P P N P N P P P P N P P N P P P N P N P P N P N N P P N P N P P N N P N N P ...
output:
Q 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 1.0 translate:success
Test #3:
score: 10
Accepted
time: 21ms
memory: 3960kb
input:
1000 0.873862 1 P P P P P P P P P P P P P P P P P P P P N P P P P P P P P P P P P P P P N P P P P P P P P P N P P P P P P P P P P P P P N P P P P P P P P P N P P P N P P N P P P P P P N P P P P P N P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P N P P P P P N P P N P P P P P P P P ...
output:
Q 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 1.0 translate:success
Test #4:
score: 10
Accepted
time: 20ms
memory: 3736kb
input:
1000 0.669578 1 P P N P P P P P N P N P P P N P P P P P P P N P P P P N N P N P N P P N P P N P P N P N P P P P P P P P P P P P P N N P P N P P N N P P N N P N P N P N P P N N P P P P P P P P P P N P P N P P N P P P P P P N P P P P N N N P N P P N P P N N P P N P P P N P P N P P P P P N P P N P P P ...
output:
Q 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 1.0 translate:success
Test #5:
score: 10
Accepted
time: 27ms
memory: 3764kb
input:
1000 0.907052 1 P P P P P P P N P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P N P P P P N P P P P P P P P P P P P N P P P P P P P P P P P P P P P P P P P P P P N P P P P P N P P P P P P P P P N P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P N P P P N P P P P N N P ...
output:
Q 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 1.0 translate:success
Test #6:
score: 10
Accepted
time: 29ms
memory: 3732kb
input:
1000 0.844418 1 P P P P P P P P P P P P N P P P P P P N P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P N P P P P P N P P P N P P P P P N P P P P P P N P P P N P N P P N P P P N P P N P P P N N N P P P P N N P N N P P P P P P P N P N P P P P N P P P P P P P P P P P P P P P P P P ...
output:
Q 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 1.0 translate:success
Test #7:
score: 10
Accepted
time: 20ms
memory: 3736kb
input:
1000 0.533576 1 P P P N N N N P P N N P N P N P P N P N N P N P N P P N P N P N P P P P N N N P P P P P N N P P N P P P P P N P P P P N N N N N P N P P P N P N P P P N P P P P N P N P P N N P N N P N P P N N P N P P N N P N N P N N P P N N N N P N P N N P N N P P N P P P P P N N N P P N P N P N P P ...
output:
Q 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 1.0 translate:success
Test #8:
score: 10
Accepted
time: 25ms
memory: 3972kb
input:
1000 0.415944 1 N N N N N N N P N N P N N P N P N N N P N N N N N N N N N P N N N N P P P P N P N N P N N P N N P P N P P P N N P N P N N N N N P N P N P N P N N N P N N N N P N N P P P P P N N N P P N N N P N N P N P P P N P P N P P P N P N P P P P P N N N P P P P P P P P N N N P P N N N N N N P P ...
output:
Q 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 1.0 translate:success
Test #9:
score: 10
Accepted
time: 30ms
memory: 3724kb
input:
1000 0.596017 1 P N P P N N P N N P P P N P N N P P P N P N P N N N P N N P N N P N P P P N P P N P P P N P N P P P N P N N P P P N P N N N P N N N P P P N P P P N N P N N P P N N P N P N N P N N P N P P N N P P P P N P P P N N P P P P P P N P P P N P P N P P P P P P P P N P P P P N N P P P N P N P ...
output:
Q 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 1.0 translate:success
Test #10:
score: 10
Accepted
time: 16ms
memory: 3788kb
input:
1000 0.157686 1 N N P P N P P N N P P P P N P N P P N N N N P P N N N P P P P P P P N P N P P P N P P P N N N P P N P N N P N N N P P P N P P N N P P N N P P N P P P P P P P P N N N P N N N P P N N N P P N N N P P N N N P N N P N N P N N N P N N N P P N P N P P N N P N N N N P P N N N N P N N P N P ...
output:
Q 1111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 1.0 translate:success
Test #11:
score: 10
Accepted
time: 30ms
memory: 3764kb
input:
1000 0.380215 1 N N N P N N N P N N P N N N P P N P N N N P P P N P P N N N P N N N P N N N P P P P N N N N N P P N N N N N N N N N N N N N N P P N N N N P P N N N P N N N N N P N P N N P N N N N P N N N N P P P P P P P N N N N N N N N N N P N N P N N N P N N N N N N N N N P N P N P N N P P N N P P ...
output:
Q 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 1.0 translate:success
Test #12:
score: 10
Accepted
time: 34ms
memory: 3720kb
input:
1000 0.432565 1 P N P N N P N N N P P P N P P N N N N N N N N N P P P N P P N N P P P P N P P N N N N P P P P N P N N P P P N N N N P N P N P N P N P P N N P N N P N N N P N P N N N P N N P N P N N N P N N P P P P P P N P N N N N N N N P P N P N N N N P P P N P N N P P P N P P P P P P N P N P P N P ...
output:
Q 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 1.0 translate:success
Test #13:
score: 10
Accepted
time: 26ms
memory: 3724kb
input:
1000 0.509199 1 P P N P N N N P P N N N N N P N N P P N P P N P P P P P N N P N P P N P P P P P P P P P P N P P P N N P N P P N P N P N N P N P N P N N N N N P P N N N P P P N N P P P P N N N N P P N P N N N P P P P P N N N P P N P P N P N P P P N N P P N N N N N N P P P N N P P N N N N N N P P N N ...
output:
Q 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 1.0 translate:success
Test #14:
score: 10
Accepted
time: 34ms
memory: 3728kb
input:
1000 0.381646 1 N N N P N N N N P P P N N N N N P N N N P N P N P N P N N N N N N N P P N N N N P P N N N N N P N N N N P N P N N N N P P P N P P N P P P N P N P P P N N N N N P N N P P N P P N P P N N N N P P N N P N N N N N P N N P P N N N N N P P N P N N P N N N P P N N P N N N N P P N N N N N P ...
output:
Q 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 1.0 translate:success
Test #15:
score: 10
Accepted
time: 25ms
memory: 3896kb
input:
1000 0.42815 1 N P P N P N P P P N N P N N P N N P P P N N N N P P P N N N P P N P N N P N N N P P N N N N P N N P P N P N N N N P N N N N N P N P P N P P P P N N N P P P N P P P N P P N P N N N P N N P N N P P N P P N N P N N P P P P P P P N N N P N P N P N N N N N N N P N N N P N P P P P N N N P N...
output:
Q 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 1.0 translate:success
Test #16:
score: 10
Accepted
time: 24ms
memory: 3676kb
input:
1000 1 1 P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P...
output:
Q 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 1.0 translate:success
Test #17:
score: 0
Runtime Error
input:
1000 0 1
output:
result:
Subtask #2:
score: 0
Time Limit Exceeded
Test #18:
score: 90
Accepted
time: 86ms
memory: 3932kb
input:
1000 0.001 300 N C P N P N N P P P N N P N C P N N P N P N P N P N P P P N N N P N N P P P N N N P N N C N C N C P P N P N P N N N P P N C P N N P P P N N N N N N C N C N C P P N P P P P N P N N N C N C P N N P N P N P P N N P P N N P P N N N N C P N P N P P N N P P N P P P N N P P N N P P N P P P P...
output:
Q 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
points 1.0 1.0 Output is correct (P=0.001, F=15.1, Q=10.7) -> 90.00 points
Test #19:
score: 90
Accepted
time: 351ms
memory: 3676kb
input:
1000 0.005256 300 P P N N N N P P P P P P N N P P N N P P P N N N P P N P N N N P N P P N P N N P P N P P N C N N N P P P P P P N N N N P P N P P P N N P P P N P N N N N N N C N N N N P N P P N N P N N N C P N N P P P N P N P N P P P P P P P P P P P N N N N N P N N P N P P N P N P N N P N P P N P N ...
output:
Q 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 1.0 Output is correct (P=0.005256, F=51.1, Q=47.7) -> 90.00 points
Test #20:
score: 90
Accepted
time: 669ms
memory: 3672kb
input:
1000 0.011546 300 P P P N N P P P P P P N N N N N N P N P N P N N P N P P N N P P P P P P P P N P P P P P P N P P N P P P N P P P N P N P N N N N N P N N N N N N N P P N N N N N P N P P N N P N N P P N P P N N P N N C N P P P P N P N N N N N P P P P P P P N N N N N P P P P P P P N P P N N P N N N N ...
output:
Q 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 1.0 Output is correct (P=0.011546, F=94.9, Q=94.4) -> 90.00 points
Test #21:
score: 85.03
Acceptable Answer
time: 1485ms
memory: 3656kb
input:
1000 0.028545 300 P P P P P P N N P P N P P N N P N N N P P P N N N N P P P P P P P P P P N N P N N P N N N N N P N P N P P N P P P N N N P N P P N P N P P P P P P P N P N P P P P P P P N P N P N P P P P P P N P P N P N N N N P P N P P N N P N P P N N P N N N P N P N P P P N N N P N P P P P N N P P ...
output:
Q 1111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 0.94477777780 0.9447777778 Output is correct (P=0.028545, F=191.5, Q=194.3) -> 85.03 points
Test #22:
score: 79.77
Acceptable Answer
time: 1963ms
memory: 3724kb
input:
1000 0.039856 300 P P N N P N P P P N N P P P P N N P N N N N N P P N P N P N P P N P N N P P P P N P P N N P P N N P N P P N P P P P P N N N N P P P P P P N P N P N P P N P N N N P P P P P P N N N N P N N N N N P P N N N N N P N P P N N N P N N N N P N P N N N N N N P P P N N N P N N N N P P P P P ...
output:
Q 1111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 0.88633333330 0.8863333333 Output is correct (P=0.039856, F=246.3, Q=254.2) -> 79.77 points
Test #23:
score: 76.61
Acceptable Answer
time: 2894ms
memory: 3740kb
input:
1000 0.068648 300 N P P P P P P N P P P N N P P P N P N P P P P P P P N N P P N N P P N P P N N P P N N P N P P P P P N P N N N N P N P P N N P P P N P N N N N N P P P N P P N P N N P P P P N P N N N P N N P P N P N N P P P N N N N P P P N P P N P N N N N N P P P P P P N N N P N N P N N P N N P P P ...
output:
Q 1111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 0.85122222220 0.8512222222 Output is correct (P=0.068648, F=366.2, Q=382.2) -> 76.61 points
Test #24:
score: 75.01
Acceptable Answer
time: 4024ms
memory: 3768kb
input:
1000 0.104571 300 N N P P N N N P N N N P N P P P P P P P P N N P N P P P N P N P N P P P N P N P N P N P N N P P P P P N N P N P P P P N N N P N N N P N N P N P N N N P N P P N N N P N N P P N P P N N P N P N P P P N N P P N N N P N P N N N P N P P P N P P P N P P N P P P N P N P P N P N P N N P N ...
output:
Q 1111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 0.83344444440 0.8334444444 Output is correct (P=0.104571, F=490.3, Q=514.8) -> 75.01 points
Test #25:
score: 0
Time Limit Exceeded
input:
1000 0.158765 300 N N P N N P N P N N P N N P P N N P P N N N N N N P N P P N N N P N N N N N P P N P N N P N N N N P P N P N N P P P N N P N P N P P P P N N N N P P P N N N N P P N P P P P P P N N P P N P N N N N P P N P N P N N N P P N N P P P N P N P N P N N P N P P N N P N N P N N N P P N N N P ...
output:
Q 1111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...