oj.uz

Submission #672348

# Submission time Handle Problem Language Result Execution time Memory
672348 2022-12-15T15:35:42 Z alvingogo Flight to the Ford (BOI22_communication) C++17
98 / 100
 7707 ms 5028 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<=20){
        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;
        }
    }
    for(int i=as/2;i<as;i++){
        if(a[i]==x){
            nxt=1;
        }
    }
    for(int i=0;i<(bs+1)/2;i++){
        if(b[i]==x){
            nxt=0;
        }
    }
    for(int i=(bs+1)/2;i<bs;i++){
        if(b[i]==x){
            nxt=1;
        }
    }
    int dd;
    if(nxt==-1){
        dd=receive();
    }
    else{
        dd=send(nxt);
    }
    if(dd==0){
        for(int i=0;i<as/2;i++){
            la.push_back(a[i]);
        }
        for(int i=as/2;i<as;i++){
            lb.push_back(a[i]);
        }
        for(int i=0;i<(bs+1)/2;i++){
            la.push_back(b[i]);
        }
        return use(la,lb,x,t);
    }
    else{
        for(int i=0;i<as/2;i++){
            rb.push_back(a[i]);
        }
        for(int i=as/2;i<as;i++){
            ra.push_back(a[i]);
        }
        for(int i=(bs+1)/2;i<bs;i++){
            ra.push_back(b[i]);
        }
        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 70 ms 1784 KB Output is correct
2 Correct 145 ms 1876 KB Output is correct
3 Correct 180 ms 1848 KB Output is correct
4 Correct 88 ms 1876 KB Output is correct
5 Correct 110 ms 1800 KB Output is correct
6 Correct 316 ms 2076 KB Output is correct
7 Correct 652 ms 1908 KB Output is correct

Subtask #2
83.000035 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1296 ms 2588 KB Output is correct
2 Correct 751 ms 2424 KB Output is correct
3 Partially correct 886 ms 2480 KB Output is partially correct
4 Partially correct 1558 ms 2660 KB Output is partially correct
5 Correct 1409 ms 2704 KB Output is correct
6 Correct 1289 ms 2644 KB Output is correct
7 Partially correct 4541 ms 3532 KB Output is partially correct
8 Partially correct 7707 ms 5028 KB Output is partially correct
9 Partially correct 6596 ms 4420 KB Output is partially correct
10 Partially correct 6503 ms 4296 KB Output is partially correct
11 Partially correct 6463 ms 4284 KB Output is partially correct
12 Partially correct 6975 ms 4408 KB Output is partially correct
13 Partially correct 6946 ms 4628 KB Output is partially correct
14 Partially correct 6493 ms 4412 KB Output is partially correct
15 Correct 3449 ms 3348 KB Output is correct
16 Partially correct 7115 ms 3612 KB Output is partially correct
17 Partially correct 1703 ms 3240 KB Output is partially correct
18 Partially correct 1787 ms 3436 KB Output is partially correct
19 Correct 2003 ms 3180 KB Output is correct
20 Partially correct 1621 ms 3256 KB Output is partially correct
21 Partially correct 1839 ms 3252 KB Output is partially correct
22 Correct 1756 ms 3484 KB Output is correct
23 Correct 2971 ms 3364 KB Output is correct
24 Correct 72 ms 1792 KB Output is correct
25 Correct 103 ms 1848 KB Output is correct
26 Correct 180 ms 1800 KB Output is correct
27 Correct 93 ms 1940 KB Output is correct
28 Correct 123 ms 1944 KB Output is correct
29 Correct 295 ms 2000 KB Output is correct
30 Correct 496 ms 1796 KB Output is correct