QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#504831#9162. COVID testskwongweng#74.4 617ms4136kbC++173.1kb2024-08-04 16:32:202024-08-04 16:32:20

Judging History

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

  • [2024-08-04 16:32:20]
  • 评测
  • 测评结果:74.4
  • 用时:617ms
  • 内存:4136kb
  • [2024-08-04 16:32:20]
  • 提交

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 = ceil(n*p);
    while (t--){
        FOR(i,0,n) val[i]=false;
        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
Wrong Answer

Test #1:

score: 10
Accepted
time: 11ms
memory: 3908kb

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: 0
Wrong Answer
time: 20ms
memory: 4136kb

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 0.0 0.0 translate:wrong

Subtask #2:

score: 74.4
Acceptable Answer

Test #18:

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

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: 36ms
memory: 4004kb

input:

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

output:

Q 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

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

Test #20:

score: 90
Accepted
time: 67ms
memory: 3920kb

input:

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

output:

Q 1111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

points 1.0 1.0 Output is correct (P=0.011546, F=94.9, Q=94.3) -> 90.00 points

Test #21:

score: 85.36
Acceptable Answer
time: 167ms
memory: 3964kb

input:

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

output:

Q 1111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

points 0.94844444440 0.9484444444 Output is correct (P=0.028545, F=191.5, Q=194.1) -> 85.36 points

Test #22:

score: 79.77
Acceptable Answer
time: 174ms
memory: 3920kb

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: 77.55
Acceptable Answer
time: 288ms
memory: 4136kb

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.86166666670 0.8616666667 Output is correct (P=0.068648, F=366.2, Q=380.9) -> 77.55 points

Test #24:

score: 76.04
Acceptable Answer
time: 386ms
memory: 3980kb

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.84488888890 0.8448888889 Output is correct (P=0.104571, F=490.3, Q=512.8) -> 76.04 points

Test #25:

score: 74.4
Acceptable Answer
time: 506ms
memory: 4136kb

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...

result:

points 0.82666666670 0.8266666667 Output is correct (P=0.158765, F=639.1, Q=672.6) -> 74.40 points

Test #26:

score: 77.57
Acceptable Answer
time: 617ms
memory: 4032kb

input:

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

output:

Q 1111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

points 0.86188888890 0.8618888889 Output is correct (P=0.2, F=731.4, Q=760.7) -> 77.57 points