oj.uz

Submission #672350

# Submission time Handle Problem Language Result Execution time Memory
672350 2022-12-15T15:50:01 Z alvingogo Flight to the Ford (BOI22_communication) C++17
100 / 100
 7602 ms 4808 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]={"00","01","11"};
            if(u==-1){
                string z;
                for(int j=0;j<2;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<2;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<2;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;
        }
    }
    for(int i=as/2;i<as;i++){
        if(a[i]==x){
            nxt=1;
        }
    }
    for(int i=0;i<(bs+1)/2;i++){
        if(b[i]==x){
            nxt=0;
        }
    }
    for(int i=(bs+1)/2;i<bs;i++){
        if(b[i]==x){
            nxt=1;
        }
    }
    int dd;
    if(nxt==-1){
        dd=receive();
    }
    else{
        dd=send(nxt);
    }
    if(dd==0){
        for(int i=0;i<as/2;i++){
            la.push_back(a[i]);
        }
        for(int i=as/2;i<as;i++){
            lb.push_back(a[i]);
        }
        for(int i=0;i<(bs+1)/2;i++){
            la.push_back(b[i]);
        }
        return use(la,lb,x,t);
    }
    else{
        for(int i=0;i<as/2;i++){
            rb.push_back(a[i]);
        }
        for(int i=as/2;i<as;i++){
            ra.push_back(a[i]);
        }
        for(int i=(bs+1)/2;i<bs;i++){
            ra.push_back(b[i]);
        }
        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 79 ms 1800 KB Output is correct
2 Correct 123 ms 1976 KB Output is correct
3 Correct 190 ms 2060 KB Output is correct
4 Correct 84 ms 1860 KB Output is correct
5 Correct 131 ms 1856 KB Output is correct
6 Correct 317 ms 2004 KB Output is correct
7 Correct 554 ms 1792 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1294 ms 2336 KB Output is correct
2 Correct 730 ms 2340 KB Output is correct
3 Correct 955 ms 2480 KB Output is correct
4 Correct 1556 ms 2680 KB Output is correct
5 Correct 1492 ms 2516 KB Output is correct
6 Correct 1176 ms 2440 KB Output is correct
7 Correct 4281 ms 3552 KB Output is correct
8 Correct 7602 ms 4808 KB Output is correct
9 Correct 6250 ms 4056 KB Output is correct
10 Correct 6597 ms 4180 KB Output is correct
11 Correct 6411 ms 4224 KB Output is correct
12 Correct 6565 ms 4568 KB Output is correct
13 Correct 6321 ms 4036 KB Output is correct
14 Correct 6367 ms 4096 KB Output is correct
15 Correct 3263 ms 3252 KB Output is correct
16 Correct 6904 ms 3744 KB Output is correct
17 Correct 1725 ms 3248 KB Output is correct
18 Correct 1665 ms 3184 KB Output is correct
19 Correct 1621 ms 3208 KB Output is correct
20 Correct 1787 ms 3204 KB Output is correct
21 Correct 1701 ms 3064 KB Output is correct
22 Correct 1866 ms 3004 KB Output is correct
23 Correct 2827 ms 3232 KB Output is correct
24 Correct 70 ms 1892 KB Output is correct
25 Correct 95 ms 1828 KB Output is correct
26 Correct 172 ms 1884 KB Output is correct
27 Correct 95 ms 1764 KB Output is correct
28 Correct 126 ms 1980 KB Output is correct
29 Correct 330 ms 2004 KB Output is correct
30 Correct 568 ms 1896 KB Output is correct