| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 839745 | 2023-08-30T15:49:47 Z | model_code | Longest Trip (IOI23_longesttrip) | C++17 | 156 ms | 440 KB |
// partially_correct/solution-NlogN.cpp
#include "longesttrip.h"
#include <algorithm>
#include <random>
#include <deque>
#include <iostream>
int N;
void findEdge(std::deque<int> &line1)
{
std::vector<int> line2;
line2.clear();
for (int i = 0; i < N; i++)
{
bool found = false;
for (int j : line1)
{
if (i == j)
{
found = true;
break;
}
}
if (!found)
line2.push_back(i);
}
std::vector<int> l1;
l1.clear();
for (int i : line1)
l1.push_back(i);
if (!are_connected(l1, line2))
return;
int pos = 0;
if (are_connected({line1.back()}, line2))
{
pos = line1.size() - 1;
}
else if (are_connected({line1.front()}, line2))
{
pos = 0;
}
else
{
int a = 0, b = line1.size() - 1;
while (a != b)
{
std::vector<int> vec(line1.begin() + a, line1.begin() + (a + b) / 2 + 1);
if (are_connected(vec, line2))
{
b = (a + b) / 2;
}
else
{
a = (a + b) / 2 + 1;
}
}
pos = a;
}
int a = 0, b = line2.size() - 1;
while (a != b)
{
std::vector<int> vec(line2.begin() + a, line2.begin() + (a + b) / 2 + 1);
if (are_connected({line1[pos]}, vec))
{
b = (a + b) / 2;
}
else
{
a = (a + b) / 2 + 1;
}
}
if (pos != (int)line1.size() - 1 && pos != 0)
std::rotate(line1.begin(), line1.begin() + pos + 1, line1.end());
if (pos == 0)
{
line1.push_front(line2[a]);
}
else
{
line1.push_back(line2[a]);
}
}
std::vector<int> longest_trip(int NN, int /*D*/)
{
N = NN;
srand(time(0));
std::deque<int> line;
line.clear();
line.push_back(rand() % N);
for (int i = 1; i < N; i++)
{
findEdge(line);
}
std::vector<int> ans;
ans.clear();
if ((int)line.size() < (N + 1) / 2)
{
for (int i = 0; i < N; i++)
{
bool found = false;
for (int j : line)
{
if (i == j)
{
found = true;
break;
}
}
if (!found)
ans.push_back(i);
}
}
else
{
for (int i : line)
ans.push_back(i);
}
return ans;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 208 KB | Output is correct |
| 2 | Correct | 30 ms | 316 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 14 ms | 236 KB | Output is correct |
| 2 | Correct | 26 ms | 208 KB | Output is correct |
| 3 | Correct | 35 ms | 208 KB | Output is correct |
| 4 | Correct | 80 ms | 304 KB | Output is correct |
| 5 | Correct | 144 ms | 320 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 18 ms | 208 KB | Output is correct |
| 2 | Correct | 38 ms | 208 KB | Output is correct |
| 3 | Correct | 63 ms | 208 KB | Output is correct |
| 4 | Correct | 90 ms | 208 KB | Output is correct |
| 5 | Correct | 132 ms | 336 KB | Output is correct |
| 6 | Correct | 24 ms | 208 KB | Output is correct |
| 7 | Correct | 35 ms | 256 KB | Output is correct |
| 8 | Correct | 64 ms | 208 KB | Output is correct |
| 9 | Correct | 68 ms | 300 KB | Output is correct |
| 10 | Correct | 131 ms | 320 KB | Output is correct |
| 11 | Correct | 124 ms | 312 KB | Output is correct |
| 12 | Correct | 139 ms | 312 KB | Output is correct |
| 13 | Correct | 109 ms | 324 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 ms | 208 KB | Output is correct |
| 2 | Correct | 32 ms | 208 KB | Output is correct |
| 3 | Correct | 66 ms | 208 KB | Output is correct |
| 4 | Correct | 73 ms | 300 KB | Output is correct |
| 5 | Correct | 133 ms | 320 KB | Output is correct |
| 6 | Correct | 14 ms | 208 KB | Output is correct |
| 7 | Correct | 27 ms | 208 KB | Output is correct |
| 8 | Correct | 62 ms | 208 KB | Output is correct |
| 9 | Correct | 84 ms | 304 KB | Output is correct |
| 10 | Correct | 111 ms | 340 KB | Output is correct |
| 11 | Correct | 150 ms | 308 KB | Output is correct |
| 12 | Correct | 135 ms | 324 KB | Output is correct |
| 13 | Correct | 122 ms | 320 KB | Output is correct |
| 14 | Correct | 13 ms | 208 KB | Output is correct |
| 15 | Correct | 16 ms | 208 KB | Output is correct |
| 16 | Correct | 36 ms | 208 KB | Output is correct |
| 17 | Correct | 56 ms | 208 KB | Output is correct |
| 18 | Correct | 55 ms | 208 KB | Output is correct |
| 19 | Correct | 46 ms | 208 KB | Output is correct |
| 20 | Correct | 79 ms | 208 KB | Output is correct |
| 21 | Correct | 126 ms | 324 KB | Output is correct |
| 22 | Correct | 112 ms | 332 KB | Output is correct |
| 23 | Correct | 119 ms | 316 KB | Output is correct |
| 24 | Correct | 117 ms | 208 KB | Output is correct |
| 25 | Correct | 23 ms | 208 KB | Output is correct |
| 26 | Correct | 10 ms | 208 KB | Output is correct |
| 27 | Correct | 28 ms | 208 KB | Output is correct |
| 28 | Correct | 33 ms | 208 KB | Output is correct |
| 29 | Correct | 45 ms | 212 KB | Output is correct |
| 30 | Correct | 49 ms | 208 KB | Output is correct |
| 31 | Correct | 44 ms | 208 KB | Output is correct |
| 32 | Correct | 46 ms | 208 KB | Output is correct |
| 33 | Correct | 73 ms | 208 KB | Output is correct |
| 34 | Correct | 77 ms | 208 KB | Output is correct |
| 35 | Correct | 67 ms | 208 KB | Output is correct |
| 36 | Correct | 143 ms | 316 KB | Output is correct |
| 37 | Correct | 138 ms | 320 KB | Output is correct |
| 38 | Correct | 112 ms | 316 KB | Output is correct |
| 39 | Correct | 112 ms | 332 KB | Output is correct |
| 40 | Correct | 100 ms | 316 KB | Output is correct |
| 41 | Correct | 86 ms | 332 KB | Output is correct |
| 42 | Correct | 102 ms | 328 KB | Output is correct |
| 43 | Correct | 90 ms | 336 KB | Output is correct |
| 44 | Correct | 101 ms | 396 KB | Output is correct |
| 45 | Correct | 24 ms | 208 KB | Output is correct |
| 46 | Correct | 20 ms | 208 KB | Output is correct |
| 47 | Correct | 33 ms | 208 KB | Output is correct |
| 48 | Correct | 29 ms | 208 KB | Output is correct |
| 49 | Correct | 39 ms | 208 KB | Output is correct |
| 50 | Correct | 63 ms | 208 KB | Output is correct |
| 51 | Correct | 57 ms | 208 KB | Output is correct |
| 52 | Correct | 76 ms | 208 KB | Output is correct |
| 53 | Correct | 82 ms | 292 KB | Output is correct |
| 54 | Correct | 74 ms | 208 KB | Output is correct |
| 55 | Correct | 67 ms | 300 KB | Output is correct |
| 56 | Correct | 113 ms | 312 KB | Output is correct |
| 57 | Correct | 127 ms | 316 KB | Output is correct |
| 58 | Correct | 144 ms | 324 KB | Output is correct |
| 59 | Correct | 142 ms | 312 KB | Output is correct |
| 60 | Correct | 143 ms | 316 KB | Output is correct |
| 61 | Correct | 139 ms | 312 KB | Output is correct |
| 62 | Correct | 143 ms | 320 KB | Output is correct |
| 63 | Correct | 128 ms | 320 KB | Output is correct |
| 64 | Correct | 121 ms | 304 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 208 KB | Output is correct |
| 2 | Correct | 27 ms | 208 KB | Output is correct |
| 3 | Correct | 61 ms | 208 KB | Output is correct |
| 4 | Partially correct | 87 ms | 208 KB | Output is partially correct |
| 5 | Partially correct | 125 ms | 320 KB | Output is partially correct |
| 6 | Correct | 15 ms | 208 KB | Output is correct |
| 7 | Correct | 19 ms | 208 KB | Output is correct |
| 8 | Correct | 46 ms | 256 KB | Output is correct |
| 9 | Partially correct | 71 ms | 208 KB | Output is partially correct |
| 10 | Partially correct | 145 ms | 316 KB | Output is partially correct |
| 11 | Partially correct | 144 ms | 312 KB | Output is partially correct |
| 12 | Partially correct | 140 ms | 376 KB | Output is partially correct |
| 13 | Partially correct | 146 ms | 440 KB | Output is partially correct |
| 14 | Correct | 7 ms | 208 KB | Output is correct |
| 15 | Correct | 15 ms | 208 KB | Output is correct |
| 16 | Correct | 38 ms | 208 KB | Output is correct |
| 17 | Correct | 54 ms | 208 KB | Output is correct |
| 18 | Correct | 52 ms | 208 KB | Output is correct |
| 19 | Partially correct | 81 ms | 308 KB | Output is partially correct |
| 20 | Partially correct | 85 ms | 336 KB | Output is partially correct |
| 21 | Correct | 12 ms | 208 KB | Output is correct |
| 22 | Correct | 13 ms | 208 KB | Output is correct |
| 23 | Correct | 33 ms | 248 KB | Output is correct |
| 24 | Correct | 32 ms | 208 KB | Output is correct |
| 25 | Correct | 23 ms | 208 KB | Output is correct |
| 26 | Partially correct | 54 ms | 208 KB | Output is partially correct |
| 27 | Correct | 42 ms | 208 KB | Output is correct |
| 28 | Correct | 48 ms | 208 KB | Output is correct |
| 29 | Partially correct | 70 ms | 256 KB | Output is partially correct |
| 30 | Partially correct | 72 ms | 208 KB | Output is partially correct |
| 31 | Partially correct | 60 ms | 208 KB | Output is partially correct |
| 32 | Correct | 17 ms | 208 KB | Output is correct |
| 33 | Correct | 32 ms | 208 KB | Output is correct |
| 34 | Correct | 19 ms | 208 KB | Output is correct |
| 35 | Correct | 43 ms | 208 KB | Output is correct |
| 36 | Correct | 41 ms | 208 KB | Output is correct |
| 37 | Partially correct | 60 ms | 208 KB | Output is partially correct |
| 38 | Partially correct | 71 ms | 232 KB | Output is partially correct |
| 39 | Partially correct | 75 ms | 236 KB | Output is partially correct |
| 40 | Partially correct | 70 ms | 208 KB | Output is partially correct |
| 41 | Partially correct | 66 ms | 208 KB | Output is partially correct |
| 42 | Partially correct | 83 ms | 304 KB | Output is partially correct |
| 43 | Partially correct | 120 ms | 324 KB | Output is partially correct |
| 44 | Partially correct | 134 ms | 316 KB | Output is partially correct |
| 45 | Partially correct | 152 ms | 328 KB | Output is partially correct |
| 46 | Partially correct | 146 ms | 324 KB | Output is partially correct |
| 47 | Partially correct | 135 ms | 328 KB | Output is partially correct |
| 48 | Partially correct | 122 ms | 320 KB | Output is partially correct |
| 49 | Partially correct | 140 ms | 336 KB | Output is partially correct |
| 50 | Partially correct | 85 ms | 316 KB | Output is partially correct |
| 51 | Partially correct | 100 ms | 316 KB | Output is partially correct |
| 52 | Partially correct | 85 ms | 316 KB | Output is partially correct |
| 53 | Partially correct | 99 ms | 340 KB | Output is partially correct |
| 54 | Partially correct | 102 ms | 320 KB | Output is partially correct |
| 55 | Partially correct | 102 ms | 312 KB | Output is partially correct |
| 56 | Partially correct | 120 ms | 316 KB | Output is partially correct |
| 57 | Partially correct | 139 ms | 344 KB | Output is partially correct |
| 58 | Partially correct | 128 ms | 288 KB | Output is partially correct |
| 59 | Partially correct | 95 ms | 316 KB | Output is partially correct |
| 60 | Partially correct | 98 ms | 316 KB | Output is partially correct |
| 61 | Partially correct | 116 ms | 328 KB | Output is partially correct |
| 62 | Partially correct | 131 ms | 320 KB | Output is partially correct |
| 63 | Partially correct | 137 ms | 316 KB | Output is partially correct |
| 64 | Partially correct | 142 ms | 356 KB | Output is partially correct |
| 65 | Partially correct | 111 ms | 316 KB | Output is partially correct |
| 66 | Partially correct | 102 ms | 320 KB | Output is partially correct |
| 67 | Partially correct | 120 ms | 328 KB | Output is partially correct |
| 68 | Partially correct | 130 ms | 348 KB | Output is partially correct |
| 69 | Partially correct | 115 ms | 316 KB | Output is partially correct |
| 70 | Partially correct | 128 ms | 316 KB | Output is partially correct |
| 71 | Partially correct | 109 ms | 332 KB | Output is partially correct |
| 72 | Partially correct | 115 ms | 316 KB | Output is partially correct |
| 73 | Partially correct | 144 ms | 320 KB | Output is partially correct |
| 74 | Partially correct | 134 ms | 320 KB | Output is partially correct |
| 75 | Partially correct | 115 ms | 316 KB | Output is partially correct |
| 76 | Partially correct | 151 ms | 320 KB | Output is partially correct |
| 77 | Partially correct | 118 ms | 336 KB | Output is partially correct |
| 78 | Partially correct | 131 ms | 332 KB | Output is partially correct |
| 79 | Partially correct | 141 ms | 328 KB | Output is partially correct |
| 80 | Partially correct | 156 ms | 316 KB | Output is partially correct |
| 81 | Partially correct | 122 ms | 208 KB | Output is partially correct |
| 82 | Partially correct | 116 ms | 208 KB | Output is partially correct |