oj.uz

Submission #672257

# Submission time Handle Problem Language Result Execution time Memory
672257 2022-12-15T09:03:02 Z alvingogo Flight to the Ford (BOI22_communication) C++17
88 / 100
 4186 ms 3080 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<=6){
        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+bs==3){
        vector<int> g;
        for(auto h:a){
            g.push_back(h);
        }
        for(auto h:b){
            g.push_back(h);
        }
        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]={"1111","0001","1000"};
            if(u==-1){
                string z;
                for(int j=0;j<4;j++){
                    z+=char('0'+receive());
                }
                int flag=-1;
                for(int i=0;i<3;i++){
                    int lst=0;
                    for(int j=0;j<4;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<4;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=31638,Bd2=178;
vector<int> emp;
vector<int> solve2(int N,int X){
    int a=-1,c=-1;
    if(X!=-1){
        a=X/Bd2;
        c=X%Bd2;
    }
    vector<int> v(max(3,N/Bd2+1));
    iota(v.begin(),v.end(),0);
    auto e=use(v,emp,a,0);
    vector<int> w(Bd2);
    iota(w.begin(),w.end(),0);
    auto f=use(w,emp,c,0);
    vector<int> z;
    for(auto h:e){
        for(auto y:f){
            if(h*Bd2+y<0 || h*Bd2+y>=N){
                continue;
            }
            z.push_back(h*Bd2+y);
        }
    }
    sort(z.begin(),z.end());
    return z;
}
vector<int> solve(int N,int X){
    int a=-1,c=-1;
    if(X!=-1){
        a=X/Bd;
        c=X%Bd;
    }
    auto e=solve2(max(3,N/Bd+1),a);
    auto f=solve2(Bd,c);
    vector<int> z;
    for(auto h:e){
        for(auto y:f){
            if(h*Bd+y<=0 || h*Bd+y>N){
                continue;
            }
            z.push_back(h*Bd+y);
        }
    }
    sort(z.begin(),z.end());
    z.erase(unique(z.begin(),z.end()),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],h[min(x-1,1)]};
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 1832 KB Output is correct
2 Correct 83 ms 1888 KB Output is correct
3 Correct 109 ms 1868 KB Output is correct
4 Correct 55 ms 1696 KB Output is correct
5 Correct 93 ms 1768 KB Output is correct
6 Correct 221 ms 2068 KB Output is correct
7 Correct 381 ms 1884 KB Output is correct

Subtask #2
73.00004 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 914 ms 2104 KB Output is partially correct
2 Partially correct 423 ms 1908 KB Output is partially correct
3 Partially correct 489 ms 1912 KB Output is partially correct
4 Partially correct 1094 ms 1932 KB Output is partially correct
5 Partially correct 674 ms 2020 KB Output is partially correct
6 Partially correct 719 ms 2068 KB Output is partially correct
7 Partially correct 2504 ms 2304 KB Output is partially correct
8 Partially correct 4186 ms 3080 KB Output is partially correct
9 Partially correct 3788 ms 2696 KB Output is partially correct
10 Partially correct 3942 ms 2808 KB Output is partially correct
11 Partially correct 3968 ms 2808 KB Output is partially correct
12 Partially correct 3666 ms 2704 KB Output is partially correct
13 Partially correct 3535 ms 2656 KB Output is partially correct
14 Partially correct 3600 ms 2724 KB Output is partially correct
15 Partially correct 1881 ms 2260 KB Output is partially correct
16 Partially correct 4128 ms 2384 KB Output is partially correct
17 Partially correct 1041 ms 2244 KB Output is partially correct
18 Partially correct 1025 ms 2376 KB Output is partially correct
19 Partially correct 1015 ms 2200 KB Output is partially correct
20 Partially correct 1049 ms 2220 KB Output is partially correct
21 Partially correct 1000 ms 2360 KB Output is partially correct
22 Partially correct 944 ms 2260 KB Output is partially correct
23 Partially correct 1625 ms 2316 KB Output is partially correct
24 Correct 66 ms 1796 KB Output is correct
25 Correct 100 ms 1712 KB Output is correct
26 Correct 132 ms 1760 KB Output is correct
27 Correct 53 ms 1912 KB Output is correct
28 Correct 81 ms 1920 KB Output is correct
29 Correct 207 ms 1988 KB Output is correct
30 Correct 424 ms 1856 KB Output is correct