oj.uz

Submission #672347

# Submission time Handle Problem Language Result Execution time Memory
672347 2022-12-15T15:31:10 Z alvingogo Flight to the Ford (BOI22_communication) C++17
98 / 100
 7567 ms 5640 KB 
#include <bits/stdc++.h>
#include "communication.h"
using namespace std;

vector<int> use(vector<int> &a,vector<int> &b,int x,int t){
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int as=a.size();
    int bs=b.size();
    if(t==0 && as+bs<=18){
        vector<int> z;
        for(auto h:a){
            z.push_back(h);
        }
        for(auto h:b){
            z.push_back(h);
        }
        return z;
    }
    vector<int> la,ra,lb,rb;
    if(as+bs<=2){
        vector<int> z;
        for(auto h:a){
            z.push_back(h);
        }
        for(auto h:b){
            z.push_back(h);
        }
        if(z.size()==1){
            int u=z[0];
            z.push_back(u);
        }
        return z;
    }
    else if(as==2 && bs==1){
        vector<int> g;
        for(auto h:a){
            g.push_back(h);
        }
        for(auto h:b){
            g.push_back(h);
        }
        if(g[0]>g[1]){
            swap(g[0],g[1]);
        }
        //sort(g.begin(),g.end());
        int u=-1;
        for(int i=0;i<3;i++){
            if(g[i]==x){
                u=i;
            }
        }
        if(t==0){
            return g;
        }
        else{
            string s[3]={"010","101","011"};
            if(u==-1){
                string z;
                for(int j=0;j<3;j++){
                    z+=char('0'+receive());
                }
                int flag=-1;
                for(int i=0;i<3;i++){
                    int lst=0;
                    if(i==2){
                        lst=1;
                    }
                    for(int j=0;j<3;j++){
                        if(s[i][j]!=z[j]){
                            if(lst){
                                flag=i;
                                break;
                            }
                            else{
                                lst=1;
                            }
                        }
                        else{
                            lst=0;
                        }
                    }
                }
                vector<int> ret;
                for(int i=0;i<3;i++){
                    if(i!=flag){
                        ret.push_back(g[i]);
                    }
                }
                return ret;
            }
            else{
                for(int i=0;i<3;i++){
                    send(int(s[u][i]-'0'));
                }
                return vector<int>();
            }   
        }
    }
    int nxt=-1;
    for(int i=0;i<as/2;i++){
        if(a[i]==x){
            nxt=0;
        }
        la.push_back(a[i]);
        rb.push_back(a[i]);
    }
    for(int i=as/2;i<as;i++){
        if(a[i]==x){
            nxt=1;
        }
        ra.push_back(a[i]);
        lb.push_back(a[i]);
    }
    for(int i=0;i<(bs+1)/2;i++){
        if(b[i]==x){
            nxt=0;
        }
        la.push_back(b[i]);
    }
    for(int i=(bs+1)/2;i<bs;i++){
        if(b[i]==x){
            nxt=1;
        }
        ra.push_back(b[i]);
    }
    int dd;
    if(nxt==-1){
        dd=receive();
    }
    else{
        dd=send(nxt);
    }
    if(dd==0){
        return use(la,lb,x,t);
    }
    else{
        return use(ra,rb,x,t);
    }
}
const int Bd=1000;
vector<int> emp;
vector<int> solve(int N,int X){
    X--;
    int a=-1,b=-1,c=-1;
    if(X>=0){
        a=X/(Bd*Bd);
        int dd=X%(Bd*Bd);
        b=dd/Bd;
        c=dd%Bd;
    }
    vector<int> v(Bd),w(Bd),k(Bd);
    iota(v.begin(),v.end(),0);
    iota(w.begin(),w.end(),0);
    iota(k.begin(),k.end(),0);
    auto e=use(v,emp,a,0);
    auto f=use(w,emp,b,0);
    auto g=use(k,emp,c,0);
    vector<int> z;
    for(auto h:e){
        for(auto y:f){
            for(auto t:g){
                int cnt=h*Bd*Bd+y*Bd+t;
                if(cnt<0 || cnt>=N){
                    continue;
                }
                z.push_back(cnt);
            }
        }
    }
    sort(z.begin(),z.end());
    return use(z,emp,X,1);
}
void encode(int N,int X){
    solve(N,X);
}

pair<int,int> decode(int N){
    auto h=solve(N,-1);
    int x=h.size();
    return {h[0]+1,h[min(x-1,1)]+1};
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 1980 KB Output is correct
2 Correct 158 ms 1840 KB Output is correct
3 Correct 196 ms 1968 KB Output is correct
4 Correct 89 ms 1852 KB Output is correct
5 Correct 153 ms 1908 KB Output is correct
6 Correct 394 ms 2196 KB Output is correct
7 Correct 564 ms 1860 KB Output is correct

Subtask #2
83.000035 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1583 ms 2608 KB Output is correct
2 Correct 665 ms 2548 KB Output is correct
3 Partially correct 879 ms 2584 KB Output is partially correct
4 Partially correct 1376 ms 2536 KB Output is partially correct
5 Correct 1215 ms 2680 KB Output is correct
6 Correct 1132 ms 2456 KB Output is correct
7 Partially correct 4673 ms 3548 KB Output is partially correct
8 Partially correct 7567 ms 5640 KB Output is partially correct
9 Partially correct 6534 ms 5000 KB Output is partially correct
10 Partially correct 6521 ms 4488 KB Output is partially correct
11 Partially correct 6727 ms 4348 KB Output is partially correct
12 Partially correct 6404 ms 4392 KB Output is partially correct
13 Partially correct 6689 ms 4692 KB Output is partially correct
14 Partially correct 6947 ms 4472 KB Output is partially correct
15 Partially correct 3159 ms 3596 KB Output is partially correct
16 Partially correct 6906 ms 3548 KB Output is partially correct
17 Partially correct 1743 ms 3448 KB Output is partially correct
18 Partially correct 1680 ms 3872 KB Output is partially correct
19 Partially correct 1758 ms 3428 KB Output is partially correct
20 Partially correct 1756 ms 3472 KB Output is partially correct
21 Partially correct 1818 ms 3740 KB Output is partially correct
22 Partially correct 1962 ms 3628 KB Output is partially correct
23 Correct 2922 ms 3528 KB Output is correct
24 Correct 91 ms 1840 KB Output is correct
25 Correct 132 ms 1864 KB Output is correct
26 Correct 200 ms 1832 KB Output is correct
27 Correct 95 ms 1844 KB Output is correct
28 Correct 116 ms 1900 KB Output is correct
29 Correct 298 ms 2044 KB Output is correct
30 Correct 592 ms 1868 KB Output is correct