QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#504770#9162. COVID testskwongweng#0 133ms3976kbC++172.9kb2024-08-04 15:47:332024-08-04 15:47:33

Judging History

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

  • [2024-08-04 15:47:33]
  • 评测
  • 测评结果:0
  • 用时:133ms
  • 内存:3976kb
  • [2024-08-04 15:47:33]
  • 提交

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,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: 46ms
memory: 3728kb

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: 68ms
memory: 3736kb

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: 0
Wrong Answer

Test #18:

score: 90
Accepted
time: 89ms
memory: 3972kb

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

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

result:

points 0.0 0.0 translate:wrong