QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#68664	#4208. Flight to the Ford	oc	100 ✓	214ms	3864kb	C++14	4.5kb	2022-12-18 13:44:02	2023-02-03 22:40:43

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-02-03 22:40:43]
评测

测评结果：100
用时：214ms
内存：3864kb

查看

[2022-12-18 13:44:02]
提交

answer

#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<=13){
        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};
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 15

Accepted

Test #1:

score: 15

Accepted

time: 25ms

memory: 3792kb

Overall Time Limit: 500ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #2:

score: 15

Accepted

time: 12ms

memory: 3632kb

Overall Time Limit: 250ms

input:

output:

input:

output:

result:

points 1.0

Test #3:

score: 15

Accepted

time: 17ms

memory: 3672kb

Overall Time Limit: 375ms

input:

output:

input:

output:

result:

points 1.0

Test #4:

score: 15

Accepted

time: 23ms

memory: 3724kb

Overall Time Limit: 500ms

input:

output:

input:

output:

result:

points 1.0

Test #5:

score: 15

Accepted

time: 53ms

memory: 3768kb

Overall Time Limit: 2000ms

input:

output:

input:

output:

result:

points 1.0

Test #6:

score: 15

Accepted

time: 8ms

memory: 3796kb

Overall Time Limit: 250ms

input:

output:

input:

output:

result:

points 1.0

Test #7:

score: 15

Accepted

time: 12ms

memory: 3656kb

Overall Time Limit: 375ms

input:

output:

input:

output:

result:

points 1.0

Subtask #2:

score: 85

Accepted

Test #8:

score: 85

Accepted

time: 88ms

memory: 3840kb

Overall Time Limit: 2210ms

input:

output:

input:

output:

result:

points 1.0

Test #9:

score: 85

Accepted

time: 158ms

memory: 3860kb

Overall Time Limit: 2955ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #10:

score: 85

Accepted

time: 128ms

memory: 3840kb

Overall Time Limit: 2020ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #11:

score: 85

Accepted

time: 80ms

memory: 3864kb

Overall Time Limit: 1235ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #12:

score: 85

Accepted

time: 124ms

memory: 3808kb

Overall Time Limit: 2500ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #13:

score: 85

Accepted

time: 135ms

memory: 3792kb

Overall Time Limit: 2965ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #14:

score: 85

Accepted

time: 137ms

memory: 3840kb

Overall Time Limit: 2955ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #15:

score: 85

Accepted

time: 132ms

memory: 3860kb

Overall Time Limit: 2960ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #16:

score: 85

Accepted

time: 78ms

memory: 3860kb

Overall Time Limit: 1210ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #17:

score: 85

Accepted

time: 37ms

memory: 3800kb

Overall Time Limit: 1050ms

input:

output:

input:

output:

result:

points 1.0

Test #18:

score: 85

Accepted

time: 107ms

memory: 3732kb

Overall Time Limit: 2300ms

input:

output:

input:

output:

result:

points 1.0

Test #19:

score: 85

Accepted

time: 64ms

memory: 3732kb

Overall Time Limit: 1255ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #20:

score: 85

Accepted

time: 66ms

memory: 3772kb

Overall Time Limit: 1250ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #21:

score: 85

Accepted

time: 28ms

memory: 3640kb

Overall Time Limit: 250ms

input:

output:

input:

output:

result:

points 1.0

Test #22:

score: 85

Accepted

time: 70ms

memory: 3744kb

Overall Time Limit: 1230ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #23:

score: 85

Accepted

time: 154ms

memory: 3864kb

Overall Time Limit: 3210ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #24:

score: 85

Accepted

time: 65ms

memory: 3836kb

Overall Time Limit: 1300ms

input:

output:

input:

output:

result:

points 1.0

Test #25:

score: 85

Accepted

time: 214ms

memory: 3864kb

Overall Time Limit: 4995ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #26:

score: 85

Accepted

time: 49ms

memory: 3696kb

Overall Time Limit: 2000ms

input:

output:

input:

output:

result:

points 1.0

Test #27:

score: 85

Accepted

time: 89ms

memory: 3728kb

Overall Time Limit: 1220ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #28:

score: 85

Accepted

time: 106ms

memory: 3860kb

Overall Time Limit: 1710ms

input:

output:

input:

output:

result:

points 1.0

Test #29:

score: 85

Accepted

time: 130ms

memory: 3840kb

Overall Time Limit: 2355ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #30:

score: 85

Accepted

time: 133ms

memory: 3736kb

Overall Time Limit: 2960ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #31:

score: 85

Accepted

time: 118ms

memory: 3864kb

Overall Time Limit: 2965ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0