QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#533364	#4208. Flight to the Ford	bachbeo2007	100 ✓	35ms	4080kb	C++23	2.3kb	2024-08-25 20:59:36	2024-08-25 20:59:37

Judging History

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

[2024-08-25 20:59:37]
评测

测评结果：100
用时：35ms
内存：4080kb

查看

[2024-08-25 20:59:36]
提交

answer

#include"communication.h"
#include<bits/stdc++.h>
using namespace std;

struct seg{
    int sz;
    vector<array<int,2>> S; 
    seg(int s=0):sz(s){}
    seg(int l,int r):sz(r-l+1){S.push_back({l,r});}
    pair<seg,seg> split(int d){
        int ss=(sz+d)/2;
        seg L(ss),R(sz-ss);
        int cnt=0;
        for(auto [l,r]:S){
            if(cnt==ss) R.S.push_back({l,r});
            else if(cnt+r-l+1<=ss) L.S.push_back({l,r}),cnt+=r-l+1;
            else{
                int m=l+ss-cnt;
                L.S.push_back({l,m-1});
                R.S.push_back({m,r});
                cnt=ss;
            }
        }
        return {L,R};
    }
    bool query(int x){
        for(auto &[l,r]:S) if(l<=x && x<=r) return true;
        return false;
    }
    vector<int> get(){
        vector<int> res;
        for(auto &[l,r]:S) for(int i=l;i<=r;i++) res.push_back(i);
        return res;
    }
};
seg merge(seg L,seg R){
    seg res(L.sz+R.sz);
    res.S=L.S;
    res.S.insert(res.S.end(),R.S.begin(),R.S.end());
    return res;
}

void encode(int N, int X) {
    seg A(1,N),B;
    while(A.sz+B.sz>3){
        seg lA,rA,lB,rB;
        tie(lA,rA)=A.split(0),tie(lB,rB)=B.split(1);
        int bit=-1;
        if(lA.query(X) || lB.query(X)) bit=send(1);
        else bit=send(0);
        if(bit) A=merge(lA,lB),B=rA;
        else A=merge(rA,rB),B=lA;
    }
    vector<int> cur=merge(A,B).get();
    if((int)cur.size()<=2) return;
    if(cur[0]==X) send(0),send(0),send(0),send(0),send(0);
    else if(cur[1]==X) send(0),send(1),send(1),send(0);
    else send(1),send(1),send(1),send(1);
}

const int T[16] = {2, 2, 2, 2, 2, 1, 0, 0, 2, 2, 1, 0, 0, 0, 0, 0};
std::pair<int, int> decode(int N) {
    seg A(1,N),B;
    while(A.sz+B.sz>3){
        seg lA,rA,lB,rB;
        tie(lA,rA)=A.split(0),tie(lB,rB)=B.split(1);
        if(receive()) A=merge(lA,lB),B=rA;
        else A=merge(rA,rB),B=lA; 
    }
    vector<int> cur=merge(A,B).get();
    if((int)cur.size()==1) return {cur[0],cur[0]};
    else if((int)cur.size()==2) return {cur[0],cur[1]};
    else{
        int s=0;
        for(int i=0;i<4;i++) s=s<<1|receive();
        if(T[s]==0) return {cur[1],cur[2]};
        else if(T[s]==1) return {cur[0],cur[2]};
        else return {cur[0],cur[1]};
    }
    return {-1,-1};
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 15

Accepted

Test #1:

score: 15

Accepted

time: 1ms

memory: 4064kb

Overall Time Limit: 500ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #2:

score: 15

Accepted

time: 1ms

memory: 4072kb

Overall Time Limit: 250ms

input:

output:

input:

output:

result:

points 1.0

Test #3:

score: 15

Accepted

time: 1ms

memory: 3772kb

Overall Time Limit: 375ms

input:

output:

input:

output:

result:

points 1.0

Test #4:

score: 15

Accepted

time: 1ms

memory: 3824kb

Overall Time Limit: 500ms

input:

output:

input:

output:

result:

points 1.0

Test #5:

score: 15

Accepted

time: 3ms

memory: 3804kb

Overall Time Limit: 2000ms

input:

output:

input:

output:

result:

points 1.0

Test #6:

score: 15

Accepted

time: 1ms

memory: 3856kb

Overall Time Limit: 250ms

input:

output:

input:

output:

result:

points 1.0

Test #7:

score: 15

Accepted

time: 1ms

memory: 4032kb

Overall Time Limit: 375ms

input:

output:

input:

output:

result:

points 1.0

Subtask #2:

score: 85

Accepted

Test #8:

score: 85

Accepted

time: 11ms

memory: 3800kb

Overall Time Limit: 2210ms

input:

output:

input:

output:

result:

points 1.0

Test #9:

score: 85

Accepted

time: 24ms

memory: 3868kb

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: 21ms

memory: 4032kb

Overall Time Limit: 2020ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #11:

score: 85

Accepted

time: 15ms

memory: 3804kb

Overall Time Limit: 1235ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #12:

score: 85

Accepted

time: 25ms

memory: 4072kb

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: 25ms

memory: 4064kb

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: 25ms

memory: 4064kb

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: 21ms

memory: 4072kb

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: 12ms

memory: 3800kb

Overall Time Limit: 1210ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #17:

score: 85

Accepted

time: 16ms

memory: 3872kb

Overall Time Limit: 1050ms

input:

output:

input:

output:

result:

points 1.0

Test #18:

score: 85

Accepted

time: 15ms

memory: 3804kb

Overall Time Limit: 2300ms

input:

output:

input:

output:

result:

points 1.0

Test #19:

score: 85

Accepted

time: 20ms

memory: 3804kb

Overall Time Limit: 1255ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #20:

score: 85

Accepted

time: 15ms

memory: 4072kb

Overall Time Limit: 1250ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #21:

score: 85

Accepted

time: 2ms

memory: 4064kb

Overall Time Limit: 250ms

input:

output:

input:

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
167 297 42
510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
167 297 4...

result:

points 1.0

Test #22:

score: 85

Accepted

time: 16ms

memory: 3800kb

Overall Time Limit: 1230ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #23:

score: 85

Accepted

time: 35ms

memory: 3932kb

Overall Time Limit: 3210ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #24:

score: 85

Accepted

time: 15ms

memory: 3868kb

Overall Time Limit: 1300ms

input:

output:

input:

output:

result:

points 1.0

Test #25:

score: 85

Accepted

time: 31ms

memory: 4080kb

Overall Time Limit: 4995ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #26:

score: 85

Accepted

time: 8ms

memory: 4080kb

Overall Time Limit: 2000ms

input:

output:

input:

output:

result:

points 1.0

Test #27:

score: 85

Accepted

time: 9ms

memory: 3808kb

Overall Time Limit: 1220ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #28:

score: 85

Accepted

time: 14ms

memory: 4072kb

Overall Time Limit: 1710ms

input:

output:

input:

output:

result:

points 1.0

Test #29:

score: 85

Accepted

time: 27ms

memory: 3948kb

Overall Time Limit: 2355ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #30:

score: 85

Accepted

time: 22ms

memory: 4060kb

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: 28ms

memory: 4080kb

Overall Time Limit: 2965ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0