oj.uz

Submission #672250

# Submission time Handle Problem Language Result Execution time Memory
672250 2022-12-15T08:55:06 Z alvingogo Flight to the Ford (BOI22_communication) C++17
86 / 100
 4444 ms 2452 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();
    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=31647,Bd2=188;
vector<int> emp;
vector<int> solve2(int N,int X){
    int a=-1,c=-1;
    if(X!=-1){
        a=X/Bd2;
        c=X%Bd2;
    }
    vector<int> v(max(3,N/Bd2+2));
    iota(v.begin(),v.end(),0);
    auto e=use(v,emp,a,0);
    vector<int> w(Bd2);
    iota(w.begin(),w.end(),0);
    auto f=use(w,emp,c,0);
    vector<int> z;
    for(auto h:e){
        for(auto y:f){
            if(h*Bd2+y<0 || h*Bd2+y>=N){
                continue;
            }
            z.push_back(h*Bd2+y);
        }
    }
    sort(z.begin(),z.end());
    return z;
}
vector<int> solve(int N,int X){
    int a=-1,c=-1;
    if(X!=-1){
        a=X/Bd;
        c=X%Bd;
    }
    auto e=solve2(max(3,N/Bd+2),a);
    auto f=solve2(Bd,c);
    vector<int> z;
    for(auto h:e){
        for(auto y:f){
            if(h*Bd+y<=0 || h*Bd+y>N){
                continue;
            }
            z.push_back(h*Bd+y);
        }
    }
    sort(z.begin(),z.end());
    z.erase(unique(z.begin(),z.end()),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],h[min(x-1,1)]};
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 1784 KB Output is correct
2 Correct 100 ms 1776 KB Output is correct
3 Correct 132 ms 1776 KB Output is correct
4 Correct 54 ms 1800 KB Output is correct
5 Correct 81 ms 1828 KB Output is correct
6 Correct 238 ms 1968 KB Output is correct
7 Correct 471 ms 1788 KB Output is correct

Subtask #2
70.99999 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 821 ms 1936 KB Output is partially correct
2 Partially correct 408 ms 1792 KB Output is partially correct
3 Partially correct 512 ms 1768 KB Output is partially correct
4 Partially correct 929 ms 1840 KB Output is partially correct
5 Partially correct 680 ms 1920 KB Output is partially correct
6 Partially correct 710 ms 1940 KB Output is partially correct
7 Partially correct 2145 ms 2064 KB Output is partially correct
8 Partially correct 3627 ms 2452 KB Output is partially correct
9 Partially correct 3417 ms 2164 KB Output is partially correct
10 Partially correct 3438 ms 2368 KB Output is partially correct
11 Partially correct 3749 ms 2312 KB Output is partially correct
12 Partially correct 3998 ms 2280 KB Output is partially correct
13 Partially correct 3902 ms 2240 KB Output is partially correct
14 Partially correct 3826 ms 2236 KB Output is partially correct
15 Partially correct 1839 ms 2044 KB Output is partially correct
16 Partially correct 4444 ms 2120 KB Output is partially correct
17 Partially correct 924 ms 2104 KB Output is partially correct
18 Partially correct 1005 ms 1904 KB Output is partially correct
19 Partially correct 1165 ms 2096 KB Output is partially correct
20 Partially correct 1058 ms 2256 KB Output is partially correct
21 Partially correct 1047 ms 2120 KB Output is partially correct
22 Partially correct 1279 ms 2060 KB Output is partially correct
23 Partially correct 1660 ms 2076 KB Output is partially correct
24 Correct 57 ms 1812 KB Output is correct
25 Correct 130 ms 1692 KB Output is correct
26 Correct 89 ms 1972 KB Output is correct
27 Correct 80 ms 1836 KB Output is correct
28 Correct 111 ms 1856 KB Output is correct
29 Correct 225 ms 2040 KB Output is correct
30 Correct 530 ms 1920 KB Output is correct