oj.uz

Submission #672345

# Submission time Handle Problem Language Result Execution time Memory
672345 2022-12-15T15:29:19 Z alvingogo Flight to the Ford (BOI22_communication) C++17
98 / 100
 6349 ms 4184 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==2 && bs==1){
        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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 1864 KB Output is correct
2 Correct 154 ms 1876 KB Output is correct
3 Correct 192 ms 1932 KB Output is correct
4 Correct 99 ms 1984 KB Output is correct
5 Correct 138 ms 1868 KB Output is correct
6 Correct 411 ms 2328 KB Output is correct
7 Correct 898 ms 1888 KB Output is correct

Subtask #2
83.000035 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 1325 ms 2340 KB Output is partially correct
2 Correct 640 ms 2288 KB Output is correct
3 Partially correct 848 ms 2488 KB Output is partially correct
4 Partially correct 1393 ms 2252 KB Output is partially correct
5 Partially correct 1494 ms 2296 KB Output is partially correct
6 Correct 1094 ms 2096 KB Output is correct
7 Partially correct 4307 ms 2928 KB Output is partially correct
8 Partially correct 6096 ms 4184 KB Output is partially correct
9 Partially correct 6182 ms 3696 KB Output is partially correct
10 Partially correct 6180 ms 3560 KB Output is partially correct
11 Partially correct 6026 ms 3572 KB Output is partially correct
12 Partially correct 6123 ms 3400 KB Output is partially correct
13 Partially correct 6349 ms 3352 KB Output is partially correct
14 Partially correct 5856 ms 3484 KB Output is partially correct
15 Partially correct 2713 ms 2772 KB Output is partially correct
16 Partially correct 5554 ms 2720 KB Output is partially correct
17 Partially correct 1411 ms 2780 KB Output is partially correct
18 Partially correct 1457 ms 2832 KB Output is partially correct
19 Partially correct 1473 ms 2764 KB Output is partially correct
20 Correct 1423 ms 2796 KB Output is correct
21 Partially correct 1412 ms 2876 KB Output is partially correct
22 Correct 1469 ms 2788 KB Output is correct
23 Partially correct 2526 ms 2784 KB Output is partially correct
24 Correct 128 ms 1988 KB Output is correct
25 Correct 98 ms 1932 KB Output is correct
26 Correct 186 ms 1948 KB Output is correct
27 Correct 99 ms 1872 KB Output is correct
28 Correct 178 ms 1996 KB Output is correct
29 Correct 319 ms 2140 KB Output is correct
30 Correct 802 ms 1932 KB Output is correct