oj.uz

Submission #672352

# Submission time Handle Problem Language Result Execution time Memory
672352 2022-12-15T15:58:14 Z alvingogo Flight to the Ford (BOI22_communication) C++17
100 / 100
 5890 ms 3344 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]={"00","01","11"};
            if(u==-1){
                string z;
                for(int j=0;j<2;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<2;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<2;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 77 ms 1892 KB Output is correct
2 Correct 117 ms 1828 KB Output is correct
3 Correct 185 ms 1880 KB Output is correct
4 Correct 98 ms 1868 KB Output is correct
5 Correct 130 ms 1828 KB Output is correct
6 Correct 328 ms 1996 KB Output is correct
7 Correct 630 ms 1768 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 949 ms 2028 KB Output is correct
2 Correct 577 ms 2064 KB Output is correct
3 Correct 670 ms 2072 KB Output is correct
4 Correct 1263 ms 2064 KB Output is correct
5 Correct 922 ms 2052 KB Output is correct
6 Correct 1057 ms 2024 KB Output is correct
7 Correct 3505 ms 2424 KB Output is correct
8 Correct 5890 ms 3344 KB Output is correct
9 Correct 5041 ms 3052 KB Output is correct
10 Correct 5085 ms 2952 KB Output is correct
11 Correct 5161 ms 2820 KB Output is correct
12 Correct 5078 ms 2856 KB Output is correct
13 Correct 5227 ms 2920 KB Output is correct
14 Correct 5202 ms 2684 KB Output is correct
15 Correct 2556 ms 2692 KB Output is correct
16 Correct 5422 ms 2348 KB Output is correct
17 Correct 1291 ms 2364 KB Output is correct
18 Correct 1378 ms 2220 KB Output is correct
19 Correct 1462 ms 2376 KB Output is correct
20 Correct 1491 ms 2404 KB Output is correct
21 Correct 1431 ms 2412 KB Output is correct
22 Correct 1485 ms 2456 KB Output is correct
23 Correct 2176 ms 2456 KB Output is correct
24 Correct 65 ms 1940 KB Output is correct
25 Correct 125 ms 1788 KB Output is correct
26 Correct 173 ms 1796 KB Output is correct
27 Correct 80 ms 1856 KB Output is correct
28 Correct 144 ms 1796 KB Output is correct
29 Correct 320 ms 2092 KB Output is correct
30 Correct 563 ms 1800 KB Output is correct