oj.uz

Submission #672265

# Submission time Handle Problem Language Result Execution time Memory
672265 2022-12-15T09:27:10 Z alvingogo Flight to the Ford (BOI22_communication) C++17
94 / 100
 5005 ms 2908 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<=10){
        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 1852 KB Output is correct
2 Correct 141 ms 1924 KB Output is correct
3 Correct 202 ms 1948 KB Output is correct
4 Correct 95 ms 1880 KB Output is correct
5 Correct 167 ms 1936 KB Output is correct
6 Correct 323 ms 2152 KB Output is correct
7 Correct 644 ms 1964 KB Output is correct

Subtask #2
79.00002 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 1115 ms 1852 KB Output is partially correct
2 Partially correct 420 ms 2056 KB Output is partially correct
3 Partially correct 584 ms 1884 KB Output is partially correct
4 Partially correct 1050 ms 1956 KB Output is partially correct
5 Partially correct 836 ms 1956 KB Output is partially correct
6 Partially correct 806 ms 1956 KB Output is partially correct
7 Partially correct 3063 ms 2372 KB Output is partially correct
8 Partially correct 5005 ms 2908 KB Output is partially correct
9 Partially correct 4510 ms 2484 KB Output is partially correct
10 Partially correct 4241 ms 2596 KB Output is partially correct
11 Partially correct 4420 ms 2596 KB Output is partially correct
12 Partially correct 4433 ms 2556 KB Output is partially correct
13 Partially correct 4249 ms 2496 KB Output is partially correct
14 Partially correct 4393 ms 2616 KB Output is partially correct
15 Partially correct 2271 ms 2192 KB Output is partially correct
16 Partially correct 4809 ms 2188 KB Output is partially correct
17 Partially correct 1232 ms 2152 KB Output is partially correct
18 Partially correct 1053 ms 2204 KB Output is partially correct
19 Partially correct 1133 ms 2272 KB Output is partially correct
20 Partially correct 1190 ms 2240 KB Output is partially correct
21 Partially correct 1366 ms 2256 KB Output is partially correct
22 Partially correct 1198 ms 2116 KB Output is partially correct
23 Partially correct 1985 ms 2340 KB Output is partially correct
24 Correct 93 ms 1792 KB Output is correct
25 Correct 149 ms 1892 KB Output is correct
26 Correct 201 ms 1780 KB Output is correct
27 Correct 89 ms 1904 KB Output is correct
28 Correct 160 ms 1960 KB Output is correct
29 Correct 365 ms 2080 KB Output is correct
30 Correct 592 ms 1904 KB Output is correct