QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#292827#7119. Longest TripFeet_McYeet0 1ms4040kbC++172.6kb2023-12-28 14:41:012023-12-28 14:41:01

Judging History

你现在查看的是测评时间为 2023-12-28 14:41:01 的历史记录

  • [2024-04-28 09:16:12]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:0ms
  • 内存:4068kb
  • [2023-12-28 14:41:01]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:4040kb
  • [2023-12-28 14:41:01]
  • 提交

answer

#include "longesttrip.h"
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx2")
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define el << '\n'
#define nl cout << '\n'
#define spc << ' '
#define forn(i,n) for (int i=0; i<n; i++)
#define forl(i,s,e) for (int i=s; i<e; i++)
#define pb push_back
#define fi first
#define se second
#define rsz resize
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
const int inf = 1000000000;
const ll inf2 = 4000000000000000000;

vector<int> longest_trip(int N, int D) {
    int n = N;
    vector<vector<int>> ls;
    forn(i,n) ls.pb({i});
    while (sz(ls) > 2) {
        vector<int> a = ls.back();
        ls.pop_back();
        vector<int> b = ls.back();
        ls.pop_back();
        vector<int> c = ls.back();
        ls.pop_back();
        if (are_connected({a.back()}, {b.back()})) {
            reverse(all(b));
            for (int i : b) a.pb(i);
            ls.pb(a);
            ls.pb(c);
            continue;
        }
        if (are_connected({a.back()}, {c.back()})) {
            reverse(all(c));
            for (int i : c) a.pb(i);
            ls.pb(a);
            ls.pb(b);
            continue;
        }
        reverse(all(c));
        for (int i : c) b.pb(i);
        ls.pb(b);
        ls.pb(a);
    }
    auto v1 = ls.back();
    ls.pop_back();
    auto v2 = ls.back();
    ls.pop_back();
    if (!are_connected(v1, v2)) {
        if (sz(v1) < sz(v2)) swap(v1, v2);
        return v1;
    }
    if (!are_connected({v1[0]}, {v1.back()})) {
        if (are_connected({v1[0]}, {v2[0]})) reverse(all(v1));
        for (int i : v2) v1.pb(i);
        return v1;
    }
    if (sz(v2)>1 && !are_connected({v2[0]}, {v2.back()})) {
        if(are_connected({v1[0]}, {v2[0]})) reverse(all(v2));
        for (int i : v1) v2.pb(i);
        return v2;
    }
    int l = 0, h = sz(v1);
    while (h-l > 1) {
        int m = (l+h)/2;
        vector<int> vt;
        forl(i,l,m) vt.pb(v1[i]);
        if (are_connected(vt, v2)) h = m;
        else l = m;
    }
    int i1 = l;
    l = 0; h = sz(v2);
    while (h-l > 1) {
        int m = (l+h)/2;
        vector<int> vt;
        forl(i,l,m) vt.pb(v2[i]);
        if (are_connected({v1[i1]}, vt)) h = m;
        else l = m;
    }
    int i2 = l;
    vector<int> ret;
    forl(i,i1+1,sz(v1)) ret.pb(v1[i]);
    forn(i,i1+1) ret.pb(v1[i]);
    forl(i,i2,sz(v2)) ret.pb(v2[i]);
    forn(i,i2) ret.pb(v2[i]);
    return ret;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3820kb

input:

341
3 3
1
1

output:

3kC2Ia2048BfyJVGojMUKKtilctlZKcB
0 1 1 2 1
3kC2Ia2048BfyJVGojMUKKtilctlZKcB
0 1 2 0 2 1
3kC2Ia2048BfyJVGojMUKKtilctlZKcB
0 1 1 0 0

result:

wrong answer non-disjoint arrays

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 0ms
memory: 3728kb

input:

341
3 2
1
1

output:

3kC2Ia2048BfyJVGojMUKKtilctlZKcB
0 1 1 2 1
3kC2Ia2048BfyJVGojMUKKtilctlZKcB
0 1 2 0 2 1
3kC2Ia2048BfyJVGojMUKKtilctlZKcB
0 1 1 0 0

result:

wrong answer non-disjoint arrays

Subtask #3:

score: 0
Wrong Answer

Test #19:

score: 0
Wrong Answer
time: 1ms
memory: 4040kb

input:

341
3 1
1
1

output:

3kC2Ia2048BfyJVGojMUKKtilctlZKcB
0 1 1 2 1
3kC2Ia2048BfyJVGojMUKKtilctlZKcB
0 1 2 0 2 1
3kC2Ia2048BfyJVGojMUKKtilctlZKcB
0 1 1 0 0

result:

wrong answer non-disjoint arrays

Subtask #4:

score: 0
Wrong Answer

Test #83:

score: 0
Wrong Answer
time: 0ms
memory: 3816kb

input:

341
3 1
1
1

output:

3kC2Ia2048BfyJVGojMUKKtilctlZKcB
0 1 1 2 1
3kC2Ia2048BfyJVGojMUKKtilctlZKcB
0 1 2 0 2 1
3kC2Ia2048BfyJVGojMUKKtilctlZKcB
0 1 1 0 0

result:

wrong answer non-disjoint arrays