oj.uz

Submission #672267

# Submission time Handle Problem Language Result Execution time Memory
672267 2022-12-15T09:31:14 Z alvingogo Flight to the Ford (BOI22_communication) C++17
96 / 100
 5994 ms 4072 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);
        }
        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=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 92 ms 1900 KB Output is correct
2 Correct 92 ms 1828 KB Output is correct
3 Correct 143 ms 1836 KB Output is correct
4 Correct 82 ms 1816 KB Output is correct
5 Correct 126 ms 1832 KB Output is correct
6 Correct 343 ms 2248 KB Output is correct
7 Correct 738 ms 1912 KB Output is correct

Subtask #2
80.999985 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 906 ms 2256 KB Output is partially correct
2 Partially correct 678 ms 2076 KB Output is partially correct
3 Partially correct 659 ms 2300 KB Output is partially correct
4 Partially correct 1259 ms 2276 KB Output is partially correct
5 Partially correct 1154 ms 2212 KB Output is partially correct
6 Partially correct 915 ms 2188 KB Output is partially correct
7 Partially correct 3711 ms 3088 KB Output is partially correct
8 Partially correct 5994 ms 4072 KB Output is partially correct
9 Partially correct 5086 ms 3752 KB Output is partially correct
10 Partially correct 5386 ms 3476 KB Output is partially correct
11 Partially correct 5286 ms 3480 KB Output is partially correct
12 Partially correct 5388 ms 3420 KB Output is partially correct
13 Partially correct 5361 ms 3500 KB Output is partially correct
14 Partially correct 5255 ms 3572 KB Output is partially correct
15 Partially correct 2790 ms 2756 KB Output is partially correct
16 Partially correct 5634 ms 3020 KB Output is partially correct
17 Partially correct 1501 ms 2984 KB Output is partially correct
18 Partially correct 1561 ms 2904 KB Output is partially correct
19 Partially correct 1461 ms 2728 KB Output is partially correct
20 Partially correct 1371 ms 2896 KB Output is partially correct
21 Partially correct 1444 ms 2876 KB Output is partially correct
22 Partially correct 1549 ms 2796 KB Output is partially correct
23 Partially correct 2393 ms 2748 KB Output is partially correct
24 Correct 89 ms 1808 KB Output is correct
25 Correct 124 ms 1824 KB Output is correct
26 Correct 180 ms 1940 KB Output is correct
27 Correct 98 ms 1952 KB Output is correct
28 Correct 146 ms 1832 KB Output is correct
29 Correct 378 ms 2012 KB Output is correct
30 Correct 740 ms 1824 KB Output is correct