QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#108802	#67. Two Transportations	bashkort^#	0	7ms	4176kb	C++20	4.2kb	2023-05-26 17:49:04	2024-05-31 13:43:38

Judging History

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

[2024-05-31 13:43:38]
评测

测评结果：0
用时：7ms
内存：4176kb

查看

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

[2023-05-26 17:49:04]
提交

Azer

#include "Azer.h"
#include <bits/stdc++.h>

using namespace std;

namespace {
    constexpr int maxN = 2000, maxQ = 58001;
    constexpr int inf = 1e9 + 7;

    int N, A, Q = 0, S = 0, usedCnt = 0;

    vector<pair<int, int>> adj[maxN];
    set<pair<int, int>> st;

    int dist[maxN];
    bool used[maxN], b[maxQ];
}

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
    ::N = N, ::A = A;

    fill(dist, dist + N, inf);
    dist[0] = 0;
    used[0] = true;


    for (int i = 0; i < A; ++i) {
        adj[U[i]].emplace_back(V[i], C[i]);
        adj[V[i]].emplace_back(U[i], C[i]);
    }

    for (auto [to, w] : adj[0]) {
        if (dist[to] > dist[0] + w) {
            st.erase({dist[to], to});
            st.emplace(dist[to] = dist[0] + w, to);
        }
    }

    for (int i = 0; i < 20; ++i) {
        SendA(0);
    }
}

void ReceiveA(bool x) {
    b[Q++] = x;

    if (Q % 20 == 0) {
        int v = 0, d = 0, s = Q - 20;

        for (int i = 0; i < 11; ++i) {
            v |= b[s + i] << i;
        }
        for (int i = 0; i < 9; ++i) {
            d |= b[s + 11 + i] << i;
        }


//        cerr << "A received: " << v << "; dist0 = " << S + d << "; diff = " << d << endl;

        if (v != 0) {
            st.erase({dist[v], v});
            st.emplace(dist[v] = min(dist[v], S + d), v);
        }

        if (st.empty()) {
            return;
        }

        auto [dis, to] = *st.begin();
        st.erase(st.begin());
        assert(!used[to]);
        used[to] = true;

        for (auto [t, w] : adj[to]) {
            if (!used[t] && dist[t] > dist[to] + w) {
                st.erase({dist[t], t});
                st.emplace(dist[t] = dist[to] + w, t);
            }
        }

        int diff = dis - S;
        S = dis;

        for (int i = 0; i < 11; ++i) {
            SendA(to >> i & 1);
        }
        for (int i = 0; i < 9; ++i) {
            SendA(diff >> i & 1);
        }
    }
}

std::vector<int> Answer() {
    std::vector<int> ans(N);
    for (int k = 0; k < N; ++k) {
        ans[k] = dist[k];
    }
    return ans;
}

Source code, Language: C++20

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>

using namespace std;

namespace {
    constexpr int maxN = 2000, maxQ = 58000;
    constexpr int inf = 1e9 + 7;

    int N, B, Q = 0, S = 0;

    vector<pair<int, int>> adj[maxN];
    set<pair<int, int>> st;

    int dist[maxN];
    bool used[maxN], b[maxQ];
}

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
    ::N = N, ::B = B;

    fill(dist, dist + N, inf);

    for (int i = 0; i < B; ++i) {
        adj[S[i]].emplace_back(T[i], D[i]);
        adj[T[i]].emplace_back(S[i], D[i]);
    }
}

void ReceiveB(bool y) {
    b[Q++] = y;

    if (Q % 20 == 0) {
        int v = 0, d = 0, s = Q - 20;

        for (int i = 0; i < 11; ++i) {
            v |= b[s + i] << i;
        }
        for (int i = 0; i < 9; ++i) {
            d |= b[s + 11 + i] << i;
        }

        S += d;
        used[v] = true;
        st.erase({dist[v], v});
        dist[v] = S;

//        cerr << "B received: " << v << "; dist0 = " << S << "; diff = " << d << endl;

        for (auto [to, w] : adj[v]) {
//            cerr << v << " " << to << " " << w << endl;
            if (!used[to] && dist[to] > dist[v] + w) {
                st.erase({dist[to], to});
                st.emplace(dist[to] = dist[v] + w, to);
            }
        }
        
        int dis, to = -1;
        
        if (!st.empty()) {
            tie(dis, to) = *st.begin();
            if (dis > 500) {
                to = -1;
            }
        }

        if (to == -1) {
            for (int i = 0; i < 20; ++i) {
                SendB(0);
            }
        } else {
            st.erase(st.begin());
            assert(dis >= S);
            assert(!used[to] && dis >= S);

            for (int i = 0; i < 11; ++i) {
                SendB(to >> i & 1);
            }
            for (int i = 0; i < 9; ++i) {
                SendB((dis - S) >> i & 1);
            }
        }
    }
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 0

Wrong Answer

time: 2ms

memory: 4028kb

input:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 1 0 -1
1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0 -1
1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 -1
-1
-1

output:

-1
0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 1 0 -1
1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0 -1
1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
-1

input:

output:

result:

wrong answer 2nd lines differ - expected: '2417', found: '1000000007'

Subtask #2:

score: 0

Wrong Answer

Test #7:

score: 8

Accepted

time: 1ms

memory: 4116kb

input:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
-1
-1

output:

-1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
-1

input:

output:

result:

ok single line: '0'

Test #8:

score: 0

Wrong Answer

time: 1ms

memory: 3924kb

input:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 -1
1 0 1 0 1 0 0 1 0 1 0 1 1 1 0 0 0 1 0 1 -1
-1
-1

output:

-1
0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
-1

input:

output:

result:

wrong answer 2nd lines differ - expected: '128264', found: '1000000007'

Subtask #3:

score: 0

Wrong Answer

Test #14:

score: 0

Wrong Answer

time: 1ms

memory: 3908kb

input:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
1 1 0 0 1 1 1 0 0 0 0 1 0 0 1 1 1 0 0 1 -1
1 1 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 -1
1 1 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 -1
1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 0 0 0 0 -1
1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 1 0 0 1 -1
0 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 0 0 0 0 -1...

output:

-1
1 0 1 0 1 1 1 1 1 1 0 1 0 1 0 0 1 0 1 1 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

input:

output:

0
1000000007
1000000007
1000000007
1000000007
1000000007
1000000007
1000000007
1000000007
1000000007
1000000007
1000000007
1000000007
1000000007
1000000007
1000000007
1000000007
1000000007
1000000007
392
1000000007
1000000007
1000000007
1000000007
1000000007
1000000007
1000000007
1000000007
10000000...

result:

wrong answer 2nd lines differ - expected: '3328', found: '1000000007'

Subtask #4:

score: 0

Wrong Answer

Test #24:

score: 0

Wrong Answer

time: 1ms

memory: 3892kb

input:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 0 -1
0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 -1
0 1 1 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 0 0 -1
1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0 -1
0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 1 0 0 1 1 -1
1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 1 -1...

output:

-1
1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 0 -1
0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 -1
0 1 1 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

input:

output:

result:

wrong answer 2nd lines differ - expected: '1881', found: '1000000007'

Subtask #5:

score: 0

Wrong Answer

Test #38:

score: 0

Wrong Answer

time: 0ms

memory: 3940kb

input:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 1 1 1 1 0 1 1 1 0 0 1 1 1 1 0 1 0 0 -1
1 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 -1
1 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 -1
1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 -1
0 0 1 0 1 1 0 0 1 1 0 0 0 1 0 0 1 0 0 1 -1
0 1 1 0 1 1 1 1 0 1 0 1 1 1 0 0 0 1 0 0 -1...

output:

-1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
1 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 -1
1 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

input:

output:

result:

wrong answer 2nd lines differ - expected: '3467', found: '1000000007'

Subtask #6:

score: 0

Wrong Answer

Test #51:

score: 0

Wrong Answer

time: 1ms

memory: 4176kb

input:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
1 0 1 1 1 1 0 1 0 1 0 0 0 0 0 1 1 0 1 0 -1
-1
-1

output:

-1
1 0 1 1 1 1 0 1 0 1 0 0 0 0 0 1 1 0 1 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
-1

input:

output:

result:

wrong answer 2nd lines differ - expected: '4745', found: '1000000007'

Subtask #7:

score: 0

Wrong Answer

Test #64:

score: 0

Wrong Answer

time: 7ms

memory: 4076kb

input:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 1 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 -1
1 1 0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 0 0 1 -1
1 1 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 1 1 1 -1
1 0 1 0 1 0 1 0 0 0 1 0 1 1 0 0 1 1 0 0 -1
0 1 0 0 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 -1
0 1 0 1 0 1 0 0 0 0 0 1 0 1 1 1 1 1 0 0 -1...

output:

-1
0 0 1 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 1 1 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

input:

output:

result:

wrong answer 1st lines differ - expected: '0', found: ''