QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#292827 | #7119. Longest Trip | Feet_McYeet | 0 | 1ms | 4040kb | C++17 | 2.6kb | 2023-12-28 14:41:01 | 2023-12-28 14:41:01 |
Judging History
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