oj.uz

답안 #672259

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
672259 2022-12-15T09:06:07 Z alvingogo Flight to the Ford (BOI22_communication) C++17
90 / 100
 5869 ms 4220 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<=8){
        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=31638,Bd2=178;
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+1));
    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+1),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

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 1880 KB Output is correct
2 Correct 83 ms 1848 KB Output is correct
3 Correct 113 ms 1804 KB Output is correct
4 Correct 56 ms 1844 KB Output is correct
5 Correct 91 ms 1844 KB Output is correct
6 Correct 235 ms 2108 KB Output is correct
7 Correct 410 ms 1896 KB Output is correct

Subtask #2
75.000005 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1064 ms 2404 KB Output is partially correct
2 Partially correct 518 ms 2248 KB Output is partially correct
3 Partially correct 682 ms 2328 KB Output is partially correct
4 Partially correct 1236 ms 2224 KB Output is partially correct
5 Partially correct 902 ms 2148 KB Output is partially correct
6 Partially correct 890 ms 2236 KB Output is partially correct
7 Partially correct 3330 ms 2968 KB Output is partially correct
8 Partially correct 5869 ms 4220 KB Output is partially correct
9 Partially correct 4940 ms 3504 KB Output is partially correct
10 Partially correct 4784 ms 3748 KB Output is partially correct
11 Partially correct 4777 ms 3732 KB Output is partially correct
12 Partially correct 4734 ms 3484 KB Output is partially correct
13 Partially correct 4669 ms 3552 KB Output is partially correct
14 Partially correct 4883 ms 3488 KB Output is partially correct
15 Partially correct 2614 ms 2736 KB Output is partially correct
16 Partially correct 5444 ms 3056 KB Output is partially correct
17 Partially correct 1353 ms 2876 KB Output is partially correct
18 Partially correct 1374 ms 2992 KB Output is partially correct
19 Partially correct 1399 ms 2920 KB Output is partially correct
20 Partially correct 1473 ms 2712 KB Output is partially correct
21 Partially correct 1334 ms 2644 KB Output is partially correct
22 Partially correct 1359 ms 2944 KB Output is partially correct
23 Partially correct 2272 ms 2860 KB Output is partially correct
24 Correct 55 ms 1700 KB Output is correct
25 Correct 91 ms 1788 KB Output is correct
26 Correct 105 ms 1888 KB Output is correct
27 Correct 39 ms 1836 KB Output is correct
28 Correct 78 ms 1800 KB Output is correct
29 Correct 189 ms 2012 KB Output is correct
30 Correct 433 ms 1764 KB Output is correct