oj.uz

Submission #672261

# Submission time Handle Problem Language Result Execution time Memory
672261 2022-12-15T09:18:02 Z alvingogo Flight to the Ford (BOI22_communication) C++17
92 / 100
 6850 ms 5668 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<=9){
        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=31644,Bd2=172;
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 1700 KB Output is correct
2 Correct 81 ms 1832 KB Output is correct
3 Correct 104 ms 1764 KB Output is correct
4 Correct 59 ms 1912 KB Output is correct
5 Correct 79 ms 1824 KB Output is correct
6 Correct 209 ms 1956 KB Output is correct
7 Correct 356 ms 1768 KB Output is correct

Subtask #2
76.99997 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 1415 ms 2908 KB Output is partially correct
2 Partially correct 496 ms 2624 KB Output is partially correct
3 Partially correct 812 ms 2708 KB Output is partially correct
4 Partially correct 1328 ms 2620 KB Output is partially correct
5 Partially correct 1297 ms 2624 KB Output is partially correct
6 Partially correct 809 ms 2724 KB Output is partially correct
7 Partially correct 4092 ms 3576 KB Output is partially correct
8 Partially correct 6850 ms 5668 KB Output is partially correct
9 Partially correct 5841 ms 4604 KB Output is partially correct
10 Partially correct 5818 ms 4664 KB Output is partially correct
11 Partially correct 5951 ms 4688 KB Output is partially correct
12 Partially correct 5770 ms 4600 KB Output is partially correct
13 Partially correct 5819 ms 4644 KB Output is partially correct
14 Partially correct 6281 ms 4768 KB Output is partially correct
15 Partially correct 3203 ms 3576 KB Output is partially correct
16 Partially correct 6367 ms 3752 KB Output is partially correct
17 Partially correct 1492 ms 3520 KB Output is partially correct
18 Partially correct 1544 ms 3832 KB Output is partially correct
19 Partially correct 1646 ms 3824 KB Output is partially correct
20 Partially correct 1688 ms 3756 KB Output is partially correct
21 Partially correct 1656 ms 3740 KB Output is partially correct
22 Partially correct 1725 ms 3580 KB Output is partially correct
23 Partially correct 2701 ms 3588 KB Output is partially correct
24 Correct 66 ms 1936 KB Output is correct
25 Correct 80 ms 1952 KB Output is correct
26 Correct 94 ms 1820 KB Output is correct
27 Correct 48 ms 1772 KB Output is correct
28 Correct 84 ms 1916 KB Output is correct
29 Correct 196 ms 2040 KB Output is correct
30 Correct 330 ms 1828 KB Output is correct