QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#72303	#4208. Flight to the Ford	xinchengo	100 ✓	137ms	3756kb	C++14	4.4kb	2023-01-15 13:06:39	2023-02-03 22:43:24

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:43:24]
评测

测评结果：100
用时：137ms
内存：3756kb

查看

[2023-01-15 13:06:39]
提交

answer

#include <vector>
#include <array>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <tuple>
#include "communication.h"

using namespace std;

struct sta
{
    int siz;
    vector<pair<int, int> > it;
    sta() : siz(0), it({}) {}
    sta(int n) : siz(n), it({{1, n}}) {}
    bool contain(int x) { for (auto i : it) 
        if ( i.first <= x && x <= i.second) return true; return false; }
};
tuple<sta, sta> split(sta k, int offset) // assuming k.siz >= 1
{
    sta a1, a2;
    int ts = (k.siz + offset) / 2;
    a1.siz = ts, a2.siz = k.siz - ts;
    for(auto i : k.it)
    {
        if(i.second - i.first + 1 <= ts)
            ts -= i.second - i.first + 1, a1.it.push_back(i);
        else
        {
            if(ts != 0)
                a1.it.push_back({i.first, i.first + ts - 1});
            a2.it.push_back({i.first + ts, i.second}), ts = 0;
        }
    }
    return {a1, a2};
}
sta merge(sta a, sta b) // assuming a * b = 0
{
    sta ans;
    ans.siz = a.siz + b.siz;
    int i = 0, j = 0;
    merge(begin(a.it), end(a.it), begin(b.it), end(b.it), back_inserter(ans.it));
    // while(i < a.it.size() || j < b.it.size())
    // {
    //     if(j >= b.it.size() || a.it[i].first < b.it[j].first)
    //     {
    //         if(!ans.it.empty() && a.it[i].first == ans.it.back().second + 1)
    //             ans.it.back().second = a.it[i].second;
    //         else
    //             ans.it.push_back(a.it[i]);
    //         i++;
    //     }
    //     else
    //     {
    //         if(!ans.it.empty() && b.it[j].first == ans.it.back().second + 1)
    //             ans.it.back().second = b.it[j].second;
    //         else
    //             ans.it.push_back(b.it[j]);
    //         j++;
    //     }
    //     // cerr << "HELP ME" << rand() << '\n';
    // }
    // while(i < a.it.size())
    // {
    //     if(!ans.it.empty() && a.it[i].first == ans.it.back().second + 1)
    //         ans.it.back().second = a.it[i].second;
    //     else
    //         ans.it.push_back(a.it[i]);
    //     i++;
    // }
    // while(j < b.it.size())
    // {
    //     if(!ans.it.empty() && b.it[j].first == ans.it.back().second + 1)
    //         ans.it.back().second = b.it[j].second;
    //     else
    //         ans.it.push_back(b.it[j]);
    //     j++;
    // }
    return ans;
}
vector<int> extract(sta a)
{
    vector<int> ans;
    for(auto i : a.it)
        for(int j = i.first; j <= i.second; j++)
            ans.push_back(j);
    return ans;
}


void encode(int N, int X)
{
    sta Tc(N), Tw, FTc, STc, FTw, STw;
    while(Tc.siz + Tw.siz > 3)
    {
        tie(FTc, STc) = split(Tc, 0), tie(FTw, STw) = split(Tw, 1);
        int d = send(FTc.contain(X) || FTw.contain(X));
        if(d)
            Tc = merge(FTc, FTw), swap(Tw, STc);
        else
            Tc = merge(STc, STw), swap(Tw, FTc);
        // cerr << Tc.siz << ' ' << rand() << '\n';
        // cerr << ' ';
        // for(auto i : Tc.it)
        //     cerr << '(' << i.first << ',' << i.second << ')';
        // cerr << ' ';
        // for(auto i : Tw.it)
        //     cerr << '(' << i.first << ',' << i.second << ')';
        // cerr << '\n';
    }
    auto rval = extract(merge(Tc, Tw));
    if(rval.size() == 3)
    {
        if(X == rval[0])
            send(0), send(0), send(0), send(0);
        else if(X == rval[1])
            send(0), send(1), send(1), send(0);
        else if(X == rval[2])
            send(1), send(1), send(1), send(1);
    }
}

pair<int, int> decode(int N)
{
    sta Tc(N), Tw, FTc, STc, FTw, STw;
    while(Tc.siz + Tw.siz > 3)
    {
        tie(FTc, STc) = split(Tc, 0), tie(FTw, STw) = split(Tw, 1);
        int d = receive();
        if(d)
            Tc = merge(FTc, FTw), swap(Tw, STc);
        else
            Tc = merge(STc, STw), swap(Tw, FTc);
    }
    auto rval = extract(merge(Tc, Tw));
    if(rval.size() == 3)
    {
        int r[4], cs0 = 0, cs1 = 0;
        for(int i=0; i<4; i++)
            r[i] = receive();
        for(int i=0; i<3; i++)
            if(r[i] == 0 && r[i+1] == 0)
                cs0 = 1;
        for(int i=0; i<3; i++)
            if(r[i] == 1 && r[i+1] == 1)
                cs1 = 1;
        if(cs1)
            return {rval[1], rval[2]};
        else if(cs0)
            return {rval[0], rval[1]};
        else
            return {rval[0], rval[2]};
    }
    return {rval.front(), rval.back()};
}

源文件, 语言: C++14

详细

Subtask #1:

score: 15

Accepted

Test #1:

score: 15

Accepted

time: 5ms

memory: 3720kb

Overall Time Limit: 500ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #2:

score: 15

Accepted

time: 4ms

memory: 3620kb

Overall Time Limit: 250ms

input:

output:

input:

output:

result:

points 1.0

Test #3:

score: 15

Accepted

time: 4ms

memory: 3676kb

Overall Time Limit: 375ms

input:

output:

input:

output:

result:

points 1.0

Test #4:

score: 15

Accepted

time: 2ms

memory: 3588kb

Overall Time Limit: 500ms

input:

output:

input:

output:

result:

points 1.0

Test #5:

score: 15

Accepted

time: 18ms

memory: 3676kb

Overall Time Limit: 2000ms

input:

output:

input:

output:

result:

points 1.0

Test #6:

score: 15

Accepted

time: 4ms

memory: 3584kb

Overall Time Limit: 250ms

input:

output:

input:

output:

result:

points 1.0

Test #7:

score: 15

Accepted

time: 4ms

memory: 3752kb

Overall Time Limit: 375ms

input:

output:

input:

output:

result:

points 1.0

Subtask #2:

score: 85

Accepted

Test #8:

score: 85

Accepted

time: 59ms

memory: 3688kb

Overall Time Limit: 2210ms

input:

output:

input:

output:

result:

points 1.0

Test #9:

score: 85

Accepted

time: 74ms

memory: 3688kb

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

memory: 3664kb

Overall Time Limit: 2020ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #11:

score: 85

Accepted

time: 44ms

memory: 3672kb

Overall Time Limit: 1235ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #12:

score: 85

Accepted

time: 81ms

memory: 3688kb

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

memory: 3732kb

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

memory: 3680kb

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

memory: 3672kb

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

memory: 3688kb

Overall Time Limit: 1210ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #17:

score: 85

Accepted

time: 31ms

memory: 3724kb

Overall Time Limit: 1050ms

input:

output:

input:

output:

result:

points 1.0

Test #18:

score: 85

Accepted

time: 76ms

memory: 3532kb

Overall Time Limit: 2300ms

input:

output:

input:

output:

result:

points 1.0

Test #19:

score: 85

Accepted

time: 46ms

memory: 3624kb

Overall Time Limit: 1255ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #20:

score: 85

Accepted

time: 41ms

memory: 3628kb

Overall Time Limit: 1250ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #21:

score: 85

Accepted

time: 3ms

memory: 3588kb

Overall Time Limit: 250ms

input:

output:

input:

output:

result:

points 1.0

Test #22:

score: 85

Accepted

time: 44ms

memory: 3664kb

Overall Time Limit: 1230ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #23:

score: 85

Accepted

time: 92ms

memory: 3732kb

Overall Time Limit: 3210ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #24:

score: 85

Accepted

time: 58ms

memory: 3628kb

Overall Time Limit: 1300ms

input:

output:

input:

output:

result:

points 1.0

Test #25:

score: 85

Accepted

time: 137ms

memory: 3756kb

Overall Time Limit: 4995ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #26:

score: 85

Accepted

time: 48ms

memory: 3592kb

Overall Time Limit: 2000ms

input:

output:

input:

output:

result:

points 1.0

Test #27:

score: 85

Accepted

time: 64ms

memory: 3628kb

Overall Time Limit: 1220ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #28:

score: 85

Accepted

time: 42ms

memory: 3620kb

Overall Time Limit: 1710ms

input:

output:

input:

output:

result:

points 1.0

Test #29:

score: 85

Accepted

time: 69ms

memory: 3624kb

Overall Time Limit: 2355ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #30:

score: 85

Accepted

time: 87ms

memory: 3724kb

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

memory: 3756kb

Overall Time Limit: 2965ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0