oj.uz

Submission #672344

# Submission time Handle Problem Language Result Execution time Memory
672344 2022-12-15T15:28:01 Z alvingogo Flight to the Ford (BOI22_communication) C++17
0 / 100
 6163 ms 4100 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<=15){
        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);
        }
        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]={"010","101","011"};
            if(u==-1){
                string z;
                for(int j=0;j<3;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<3;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<3;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=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
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 356 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 1216 ms 2280 KB Output is partially correct
2 Correct 672 ms 2220 KB Output is correct
3 Partially correct 721 ms 2404 KB Output is partially correct
4 Partially correct 1382 ms 2196 KB Output is partially correct
5 Partially correct 1167 ms 2272 KB Output is partially correct
6 Correct 1004 ms 2236 KB Output is correct
7 Partially correct 4002 ms 2980 KB Output is partially correct
8 Partially correct 6163 ms 4100 KB Output is partially correct
9 Partially correct 5352 ms 3856 KB Output is partially correct
10 Partially correct 5125 ms 3400 KB Output is partially correct
11 Partially correct 5342 ms 3440 KB Output is partially correct
12 Partially correct 5007 ms 3572 KB Output is partially correct
13 Partially correct 5250 ms 3364 KB Output is partially correct
14 Partially correct 5233 ms 3384 KB Output is partially correct
15 Partially correct 2828 ms 2936 KB Output is partially correct
16 Partially correct 5874 ms 2788 KB Output is partially correct
17 Partially correct 1669 ms 2820 KB Output is partially correct
18 Partially correct 1774 ms 2908 KB Output is partially correct
19 Partially correct 1746 ms 2796 KB Output is partially correct
20 Correct 1621 ms 2760 KB Output is correct
21 Partially correct 1716 ms 2944 KB Output is partially correct
22 Correct 1698 ms 2840 KB Output is correct
23 Partially correct 2932 ms 2816 KB Output is partially correct
24 Incorrect 53 ms 364 KB Not correct
25 Halted 0 ms 0 KB -