oj.uz

Submission #1038049

# Submission time Handle Problem Language Result Execution time Memory
1038049 2024-07-29T12:29:10 Z ttamx Islands (IOI08_islands) C++17
0 / 100
 2000 ms 131076 KB 
#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,t,k;
double p;
string ans;

int ask(int l,int r){
    string s(n,'0');
    for(int i=l;i<=r;i++)s[i]='1';
    cout << "Q " << s << endl;
    char res;
    cin >> res;
    return res=='P';
}

void solve(int l,int r){
    if(l==r)return void(ans[l]='1');
    int m=(l+r)/2;
    bool found=false;
    if(rng()&1){
        if(ask(l,m)){
            solve(l,m);
            found=true;
        }
        if(!found||ask(m+1,r)){
            solve(m+1,r);
        }
    }else{
        if(ask(m+1,r)){
            solve(m+1,r);
            found=true;
        }
        if(!found||ask(l,m)){
            solve(l,m);
        }
    }
}

void runcase(){
    ans=string(n,'0');
    for(int l=0,r=k-1;l<n;l+=k,r+=k){
        r=min(r,n-1);
        if(ask(l,r))solve(l,r);
    }
    cout << "A " << ans << endl;
    string s;
    cin >> s;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> p >> t;
    double q=1-p,r=q;
    k=1;
    while(r>0.5&&k<n){
        r*=q;
        k++;
    }
    while(t--)runcase();
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2058 ms 15352 KB Time limit exceeded
2 Execution timed out 2795 ms 131072 KB Time limit exceeded
3 Execution timed out 2793 ms 131072 KB Time limit exceeded
4 Execution timed out 2096 ms 20652 KB Time limit exceeded
5 Execution timed out 2056 ms 32624 KB Time limit exceeded
6 Execution timed out 2076 ms 35456 KB Time limit exceeded
7 Execution timed out 2027 ms 98384 KB Time limit exceeded
8 Execution timed out 4123 ms 131072 KB Time limit exceeded
9 Execution timed out 3685 ms 131072 KB Time limit exceeded
10 Execution timed out 3280 ms 131072 KB Time limit exceeded
11 Execution timed out 3001 ms 131076 KB Time limit exceeded

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2364 ms 131072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2321 ms 131072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2365 ms 131072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2296 ms 131072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2330 ms 131072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2365 ms 131072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2317 ms 131072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2308 ms 131072 KB Time limit exceeded
2 Halted 0 ms 0 KB -