QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#505047#9162. COVID testskwongweng44.47 659ms4108kbC++173.1kb2024-08-04 18:44:342024-08-04 18:44:34

Judging History

你现在查看的是最新测评结果

  • [2024-08-04 18:44:34]
  • 评测
  • 测评结果:44.47
  • 用时:659ms
  • 内存:4108kb
  • [2024-08-04 18:44:34]
  • 提交

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;
vector<bool> val(N);

bool qry() {
    string mask_str(n, ' ');
    for (int i = 0; i < n; i++)
        mask_str[i] = val[i] ? '1' : '0';
    printf("Q %s\n", mask_str.c_str());
    fflush(stdout);
    char answer;
    scanf(" %c", &answer);
    return answer == '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]=true;
    }
    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] = true;
        FOR(i,mid+1,r+1) val[i] = false;
        if (qry()) l=mid;
        else r=mid;
    }
    FOR(i,L,r) val[i]=true;
    val[r] = false;
    if (r==R) return;
    find_positive(r+1,R);
}

void solve(){
    double p; int t; cin>>n>>p>>t;
    int v = floor(n*p*2);
    while (t--){
        FOR(i,0,n) val[i]=false;
        FOR(i,0,v-1) find_positive(i*(n/v), (i+1)*(n/v)-1);
        find_positive((v-1)*(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
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 20ms
memory: 3816kb

input:

1000 0.789673 1
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
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
N
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
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
...

output:

Q 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

points 0.0 0.0 translate:wrong

Subtask #2:

score: 44.47
Acceptable Answer

Test #18:

score: 90
Accepted
time: 20ms
memory: 3812kb

input:

1000 0.001 300
N
N
C
N
P
P
N
N
P
P
P
N
N
P
N
C
N
P
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
N
C
N
N
C
P
N
P
N
P
N
N
N
P
P
N
N
C
N
P
N
P
P
P
N
N
N
N
N
N
C
N
N
C
N
N
C
P
N
P
P
P
P
N
P
N
N
N
N
C
N
N
C
N
P
N
P
N
P
N
P
P
N
N
P
P
N
N
P
P
N
N
N
N
C
N
P
P
N
P
P
N
N
P
P
N
P
P
P
N
N
P
P
N
N
P...

output:

Q 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

points 1.0 1.0 Output is correct (P=0.001, F=15.1, Q=10.9) -> 90.00 points

Test #19:

score: 90
Accepted
time: 58ms
memory: 4096kb

input:

1000 0.005256 300
P
N
N
N
N
P
P
N
P
P
P
P
P
N
P
N
N
N
P
P
N
N
N
P
P
N
N
N
P
N
N
P
N
P
P
N
N
P
N
P
P
N
P
P
N
C
N
N
N
N
N
N
P
P
P
P
P
N
N
N
N
N
P
N
P
P
P
N
N
P
N
P
P
P
P
N
P
N
N
N
C
N
N
N
N
N
N
N
N
N
P
P
P
N
N
P
N
N
N
C
N
P
N
P
P
P
N
P
N
N
P
P
P
P
P
P
P
P
P
P
P
P
N
N
N
N
N
N
N
P
N
P
N
P
P
N
P
N
N
P
N
...

output:

Q 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

points 1.0 1.0 Output is correct (P=0.005256, F=51.1, Q=48.3) -> 90.00 points

Test #20:

score: 89.62
Acceptable Answer
time: 73ms
memory: 3968kb

input:

1000 0.011546 300
P
P
N
N
P
N
P
P
P
N
P
N
N
N
N
N
N
N
P
N
P
P
N
N
P
N
N
P
P
P
P
N
P
P
P
P
P
P
N
P
P
P
P
P
N
P
N
N
P
P
P
P
N
N
N
N
N
N
N
N
N
N
N
N
N
P
N
N
P
N
N
P
N
P
N
N
P
N
N
N
N
N
P
N
N
P
N
P
N
P
P
N
N
P
N
N
N
C
N
N
P
P
N
P
P
N
N
N
N
N
N
N
P
P
N
N
P
N
P
N
N
N
N
N
N
N
N
N
N
P
N
N
P
N
N
N
N
N
N
P
N
...

output:

Q 1111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

points 0.99577777780 0.9957777778 Output is correct (P=0.011546, F=94.9, Q=95.0) -> 89.62 points

Test #21:

score: 78.81
Acceptable Answer
time: 170ms
memory: 3924kb

input:

1000 0.028545 300
P
P
P
P
P
N
N
N
N
P
N
P
N
N
N
N
N
P
N
N
N
N
N
P
P
P
N
N
N
N
N
N
P
P
N
N
P
P
P
N
N
P
N
N
P
P
P
N
P
N
N
N
N
N
P
N
N
P
N
N
N
P
P
P
P
P
P
N
N
N
P
N
P
N
P
N
N
N
P
N
N
N
N
N
P
P
P
P
P
P
P
N
N
P
P
N
P
P
N
N
N
P
P
N
N
N
N
N
N
N
P
P
N
N
N
N
N
N
P
P
P
N
P
P
N
N
N
P
N
N
P
P
P
P
N
N
N
N
N
P
P
...

output:

Q 1111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

points 0.87566666670 0.8756666667 Output is correct (P=0.028545, F=191.5, Q=198.3) -> 78.81 points

Test #22:

score: 73.23
Acceptable Answer
time: 185ms
memory: 3820kb

input:

1000 0.039856 300
P
N
N
P
N
N
P
P
N
N
N
P
N
P
N
N
N
N
N
N
N
N
N
N
N
P
P
P
N
P
N
N
P
P
N
P
P
P
P
N
P
N
N
N
P
N
P
P
N
P
P
P
N
N
P
P
N
N
N
N
N
P
N
N
N
P
N
N
P
P
P
N
N
N
P
N
P
N
P
N
N
P
P
P
P
N
P
N
N
N
N
N
N
N
N
N
N
N
N
N
P
P
N
N
P
N
N
P
N
P
N
N
N
N
N
P
N
P
P
N
N
P
N
P
N
N
N
N
N
P
P
N
P
N
P
N
N
P
P
P
N
...

output:

Q 1111111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

points 0.81366666670 0.8136666667 Output is correct (P=0.039856, F=246.3, Q=260.4) -> 73.23 points

Test #23:

score: 72.31
Acceptable Answer
time: 305ms
memory: 3964kb

input:

1000 0.068648 300
N
N
P
P
P
P
N
P
N
P
P
N
P
P
P
P
N
N
P
P
P
P
P
P
P
P
N
N
P
N
N
P
N
P
N
P
P
N
N
N
P
N
N
P
N
N
P
P
P
N
P
P
N
N
N
N
N
N
P
P
P
N
N
N
P
P
N
P
N
N
N
N
N
N
N
N
N
N
P
P
N
P
N
P
N
P
P
P
P
P
P
N
N
P
N
N
P
N
N
N
P
N
P
N
N
N
P
P
N
N
N
N
N
N
P
P
N
P
N
P
N
P
P
N
N
N
N
N
P
P
P
P
N
N
N
P
N
N
P
N
N
...

output:

Q 1111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

points 0.80344444440 0.8034444444 Output is correct (P=0.068648, F=366.2, Q=388.6) -> 72.31 points

Test #24:

score: 56.35
Acceptable Answer
time: 344ms
memory: 3816kb

input:

1000 0.104571 300
N
N
N
N
N
P
P
N
N
N
N
P
N
P
N
P
P
P
P
P
N
N
N
N
N
P
N
P
N
P
P
N
N
P
N
N
P
N
P
N
N
P
P
N
N
P
P
P
P
P
N
N
P
P
P
P
N
P
N
N
N
N
N
N
N
N
N
P
P
P
N
N
N
N
P
P
P
N
N
N
N
P
P
N
N
N
N
N
N
N
N
P
N
P
N
P
P
P
N
P
P
P
P
N
N
P
N
N
N
N
P
N
P
N
N
N
P
P
N
N
N
N
N
P
N
P
N
P
P
N
P
P
N
P
N
N
N
P
P
N
N
...

output:

Q 1111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

points 0.62611111110 0.6261111111 Output is correct (P=0.104571, F=490.3, Q=563.5) -> 56.35 points

Test #25:

score: 71.37
Acceptable Answer
time: 548ms
memory: 4108kb

input:

1000 0.158765 300
N
N
N
N
N
P
N
P
N
N
P
N
P
N
N
N
P
N
N
P
P
N
N
N
N
N
N
N
N
N
N
N
N
P
P
P
N
N
N
N
N
N
P
N
N
N
N
N
N
P
N
P
N
N
N
N
N
P
N
N
N
N
P
N
P
N
N
N
N
P
P
N
N
N
N
N
P
P
N
P
P
N
P
N
N
N
N
P
P
N
N
N
N
N
N
N
N
P
N
P
P
P
P
N
N
N
P
N
P
N
N
N
N
N
N
N
N
P
N
P
N
N
N
P
N
N
P
N
N
P
P
P
N
N
P
P
N
N
P
N
P
...

output:

Q 1110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

points 0.7930 0.793 Output is correct (P=0.158765, F=639.1, Q=680.8) -> 71.37 points

Test #26:

score: 44.47
Acceptable Answer
time: 659ms
memory: 3932kb

input:

1000 0.2 300
N
N
P
P
N
N
P
N
P
N
N
N
N
N
N
N
N
N
P
N
P
N
P
P
N
N
P
N
P
N
N
P
P
N
P
P
N
N
P
P
N
P
P
N
N
P
P
P
N
N
P
N
N
P
P
N
N
N
N
N
N
N
P
N
P
P
P
N
N
P
N
N
N
P
N
N
P
N
N
P
N
N
N
N
N
N
N
P
N
P
N
P
P
N
P
N
N
N
N
P
P
P
P
N
N
P
P
N
N
N
P
P
N
P
P
N
P
P
N
N
N
N
N
N
N
P
P
P
P
P
N
P
N
N
N
N
P
N
N
N
N
N
N
P...

output:

Q 1100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

points 0.49411111110 0.4941111111 Output is correct (P=0.2, F=731.4, Q=918.6) -> 44.47 points