oj.uz

Submission #672255

# Submission time Handle Problem Language Result Execution time Memory
672255 2022-12-15T08:59:01 Z alvingogo Flight to the Ford (BOI22_communication) C++17
82 / 100
 3673 ms 2568 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();
    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=31623,Bd2=202;
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 57 ms 1872 KB Output is correct
2 Correct 101 ms 1796 KB Output is correct
3 Correct 141 ms 1848 KB Output is correct
4 Correct 66 ms 1876 KB Output is correct
5 Correct 84 ms 1860 KB Output is correct
6 Correct 295 ms 1924 KB Output is correct
7 Correct 595 ms 1916 KB Output is correct

Subtask #2
66.999975 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 776 ms 1824 KB Output is partially correct
2 Partially correct 421 ms 1880 KB Output is partially correct
3 Partially correct 434 ms 1936 KB Output is partially correct
4 Partially correct 820 ms 1912 KB Output is partially correct
5 Partially correct 756 ms 1780 KB Output is partially correct
6 Partially correct 707 ms 1768 KB Output is partially correct
7 Partially correct 2269 ms 2032 KB Output is partially correct
8 Partially correct 3673 ms 2568 KB Output is partially correct
9 Partially correct 3188 ms 2480 KB Output is partially correct
10 Partially correct 3030 ms 2240 KB Output is partially correct
11 Partially correct 3205 ms 2256 KB Output is partially correct
12 Partially correct 2961 ms 2360 KB Output is partially correct
13 Partially correct 3204 ms 2172 KB Output is partially correct
14 Partially correct 3050 ms 2264 KB Output is partially correct
15 Partially correct 1832 ms 2208 KB Output is partially correct
16 Partially correct 3651 ms 2040 KB Output is partially correct
17 Partially correct 891 ms 2132 KB Output is partially correct
18 Partially correct 898 ms 2004 KB Output is partially correct
19 Partially correct 837 ms 1972 KB Output is partially correct
20 Partially correct 886 ms 2204 KB Output is partially correct
21 Partially correct 955 ms 2048 KB Output is partially correct
22 Partially correct 956 ms 1904 KB Output is partially correct
23 Partially correct 1567 ms 1932 KB Output is partially correct
24 Correct 50 ms 1784 KB Output is correct
25 Correct 84 ms 1964 KB Output is correct
26 Correct 110 ms 1844 KB Output is correct
27 Correct 60 ms 1832 KB Output is correct
28 Correct 103 ms 1868 KB Output is correct
29 Correct 257 ms 2044 KB Output is correct
30 Correct 496 ms 1768 KB Output is correct