oj.uz

Submission #672266

# Submission time Handle Problem Language Result Execution time Memory
672266 2022-12-15T09:29:14 Z alvingogo Flight to the Ford (BOI22_communication) C++17
94 / 100
 5283 ms 3528 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<=12){
        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 84 ms 1988 KB Output is correct
2 Correct 119 ms 1876 KB Output is correct
3 Correct 169 ms 1928 KB Output is correct
4 Correct 81 ms 1836 KB Output is correct
5 Correct 154 ms 1904 KB Output is correct
6 Correct 355 ms 2072 KB Output is correct
7 Correct 684 ms 1952 KB Output is correct

Subtask #2
79.00002 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 1146 ms 2168 KB Output is partially correct
2 Partially correct 528 ms 2188 KB Output is partially correct
3 Partially correct 455 ms 2016 KB Output is partially correct
4 Partially correct 1152 ms 2116 KB Output is partially correct
5 Partially correct 941 ms 2028 KB Output is partially correct
6 Partially correct 887 ms 2048 KB Output is partially correct
7 Partially correct 3304 ms 2444 KB Output is partially correct
8 Partially correct 5283 ms 3528 KB Output is partially correct
9 Partially correct 4697 ms 2860 KB Output is partially correct
10 Partially correct 4703 ms 2980 KB Output is partially correct
11 Partially correct 4676 ms 2972 KB Output is partially correct
12 Partially correct 4730 ms 3088 KB Output is partially correct
13 Partially correct 4668 ms 2848 KB Output is partially correct
14 Partially correct 4708 ms 2868 KB Output is partially correct
15 Partially correct 2484 ms 2632 KB Output is partially correct
16 Partially correct 5154 ms 2564 KB Output is partially correct
17 Partially correct 1418 ms 2548 KB Output is partially correct
18 Partially correct 1216 ms 2444 KB Output is partially correct
19 Partially correct 1234 ms 2552 KB Output is partially correct
20 Partially correct 1338 ms 2512 KB Output is partially correct
21 Partially correct 1363 ms 2528 KB Output is partially correct
22 Partially correct 1242 ms 2600 KB Output is partially correct
23 Partially correct 2078 ms 2632 KB Output is partially correct
24 Correct 73 ms 1840 KB Output is correct
25 Correct 150 ms 2024 KB Output is correct
26 Correct 192 ms 1828 KB Output is correct
27 Correct 79 ms 1848 KB Output is correct
28 Correct 133 ms 1840 KB Output is correct
29 Correct 347 ms 2084 KB Output is correct
30 Correct 574 ms 1932 KB Output is correct