oj.uz

Submission #672351

# Submission time Handle Problem Language Result Execution time Memory
672351 2022-12-15T15:55:53 Z alvingogo Flight to the Ford (BOI22_communication) C++17
98 / 100
 5512 ms 2968 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<=13){
        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 88 ms 1872 KB Output is correct
2 Correct 110 ms 1848 KB Output is correct
3 Correct 128 ms 2044 KB Output is correct
4 Correct 78 ms 1844 KB Output is correct
5 Correct 153 ms 1848 KB Output is correct
6 Correct 303 ms 2080 KB Output is correct
7 Correct 614 ms 1864 KB Output is correct

Subtask #2
83.000035 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 919 ms 1976 KB Output is correct
2 Correct 549 ms 1940 KB Output is correct
3 Correct 613 ms 2104 KB Output is correct
4 Correct 1166 ms 1904 KB Output is correct
5 Correct 1047 ms 2044 KB Output is correct
6 Correct 809 ms 1944 KB Output is correct
7 Correct 3186 ms 2364 KB Output is correct
8 Correct 5497 ms 2968 KB Output is correct
9 Correct 4941 ms 2660 KB Output is correct
10 Correct 4688 ms 2768 KB Output is correct
11 Partially correct 4840 ms 2616 KB Output is partially correct
12 Correct 4851 ms 2820 KB Output is correct
13 Correct 4925 ms 2628 KB Output is correct
14 Correct 4850 ms 2656 KB Output is correct
15 Correct 2476 ms 2232 KB Output is correct
16 Correct 5512 ms 2348 KB Output is correct
17 Correct 1249 ms 2396 KB Output is correct
18 Correct 1308 ms 2276 KB Output is correct
19 Correct 1358 ms 2188 KB Output is correct
20 Correct 1282 ms 2348 KB Output is correct
21 Partially correct 1374 ms 2308 KB Output is partially correct
22 Correct 1354 ms 2372 KB Output is correct
23 Correct 2092 ms 2244 KB Output is correct
24 Correct 76 ms 1836 KB Output is correct
25 Correct 108 ms 1840 KB Output is correct
26 Correct 165 ms 1828 KB Output is correct
27 Correct 91 ms 1860 KB Output is correct
28 Correct 134 ms 1792 KB Output is correct
29 Correct 297 ms 2052 KB Output is correct
30 Correct 710 ms 1920 KB Output is correct