#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
bool are_connected(std::vector<int> A, std::vector<int> B);
void add(vector<int> &a,vector<int> &b){
reverse(a.begin(),a.end());
for(auto i : b)a.push_back(i);
}
bool query(vector<int> &a,vector<int> &b,int l1,int r1,int l2,int r2){
vector<int> tmp1,tmp2;
for(int i=l1;i<=r1;i++)tmp1.push_back(a[i]);
for(int i=l2;i<=r2;i++)tmp2.push_back(b[i]);
return are_connected(tmp1,tmp2);
}
bool comp1(vector<int> &a,vector<int> &b){
return a.size()<b.size();
}
bool comp2(vector<int> &a,vector<int> &b){
return a.size()>b.size();
}
mt19937 rng((uint64_t) chrono::duration_cast<chrono::
nanoseconds>(chrono::high_resolution_clock::now()
.time_since_epoch()).count());
vector<int> longest_trip(int N, int D)
{
srand(time(NULL));
deque<vector<int>> q;
for(int i=0;i<N;i++){
q.push_back({i});
}
shuffle(q.begin(),q.end(),rng);
int cont=0;
/*
while(q.size()>3){
//shuffle(q.begin(),q.end(),rng);
sort(q.begin(),q.end(),comp1);
shuffle(q.begin(),q.begin()+4,rng);
auto a = q.front();
q.pop_front();
auto b = q.front();
q.pop_front();
auto c = q.front();
q.pop_front();
auto d = q.front();
q.pop_front();
if(!are_connected({*a.begin(),*b.begin()},{*c.begin(),*d.begin()})){
add(a,b);
add(c,d);
q.push_back(a);
q.push_back(c);
continue;
}
if(!are_connected({*a.begin()},{*c.begin(),*d.begin()})){
add(c,d);
q.push_back(a);
q.push_back(b);
q.push_back(c);
continue;
}
if(are_connected({*a.begin()},{*c.begin()})){
add(a,c);
q.push_back(a);
q.push_back(b);
q.push_back(d);
continue;
}
add(a,d);
q.push_back(a);
q.push_back(b);
q.push_back(c);
}
*/
while(q.size()>2){
shuffle(q.begin()+1,q.end(),rng);
//sort(q.begin(),q.end(),comp1);
//sort(q.begin()+1,q.end(),comp2);
//shuffle(q.begin()+1,q.begin()+3,rng);
auto a = q.front();
q.pop_front();
auto b = q.front();
q.pop_front();
auto c = q.front();
q.pop_front();
//if(rng()%2)reverse(a.begin(),a.end());
if(rng()%2)reverse(b.begin(),b.end());
if(rng()%2)reverse(c.begin(),c.end());
swap(a,c);
if(are_connected({*a.begin()},{*b.begin()})){
add(a,b);
q.push_back(a);
q.push_front(c);
cont++;
}else if(are_connected({*a.begin()},{*c.begin()})){
add(a,c);
q.push_back(a);
q.push_front(b);
cont+=2;
}else{
add(b,c);
q.push_back(b);
q.push_front(a);
cont+=2;
}
}
assert(cont<400);
auto a = q.front();
q.pop_front();
auto b = q.front();
q.pop_front();
if(!are_connected(a,b)){
if(a.size()>b.size())return a;
else return b;
}else{
int l1 = *a.begin(), r1 = a.back();
int l2 = *b.begin(), r2 = b.back();
if(are_connected({l1,r1},{l2,r2})){
if(are_connected({l1},{l2})){
add(a,b);
return a;
}
if(are_connected({l1},{r2})){
reverse(b.begin(),b.end());
add(a,b);
return a;
}
if(are_connected({l2},{r1})){
reverse(a.begin(),a.end());
add(a,b);
return a;
}
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
add(a,b);
return a;
}
int low = -1, up = a.size()-1;
while(up-low>1){
int mid = (up+low)/2;
if(query(a,b,0,mid,0,b.size()-1)){
up=mid;
}else{
low=mid;
}
}
int ind = up;
low = -1, up = b.size()-1;
while(up-low>1){
int mid = (up+low)/2;
if(query(a,b,ind,ind,0,mid)){
up=mid;
}else{
low=mid;
}
}
for(int i=0;i<ind;i++){
a.push_back(*a.begin());
a.erase(a.begin());
}
for(int i=0;i<up;i++){
b.push_back(*b.begin());
b.erase(b.begin());
}
add(a,b);
return a;
}
}
/*
1
5 1
1
1 1
0 0 1
0 0 0 1
static inline constexpr int maxNumberOfCalls = 32640;
static inline constexpr int maxTotalNumberOfCalls = 150000;
static inline constexpr int maxTotalNumberOfLandmarksInCalls = 1500000;
static int call_counter = 0;
static int total_call_counter = 0;
static int landmark_counter = 0;
static int C, N, D;
static std::vector<std::vector<int>> U;
static std::vector<bool> present;
static inline void protocol_violation(std::string message)
{
printf("Protocol Violation: %s\n", message.c_str());
exit(0);
}
bool are_connected(std::vector<int> A, std::vector<int> B)
{
++call_counter;
++total_call_counter;
if (call_counter > maxNumberOfCalls || total_call_counter > maxTotalNumberOfCalls)
{
protocol_violation("too many calls");
}
int nA = A.size(), nB = B.size();
landmark_counter += nA + nB;
if (landmark_counter > maxTotalNumberOfLandmarksInCalls)
{
protocol_violation("too many elements");
}
if (nA == 0 || nB == 0)
{
protocol_violation("invalid array");
}
for (int i = 0; i < nA; ++i)
{
if (A[i] < 0 || N <= A[i])
{
protocol_violation("invalid array");
}
if (present[A[i]])
{
protocol_violation("invalid array");
}
present[A[i]] = true;
}
for (int i = 0; i < nA; ++i)
{
present[A[i]] = false;
}
for (int i = 0; i < nB; ++i)
{
if (B[i] < 0 || N <= B[i])
{
protocol_violation("invalid array");
}
if (present[B[i]])
{
protocol_violation("invalid array");
}
present[B[i]] = true;
}
for (int i = 0; i < nB; ++i)
{
present[B[i]] = false;
}
for (int i = 0; i < nA; ++i)
{
for (int j = 0; j < nB; ++j)
{
if (A[i] == B[j])
{
protocol_violation("non-disjoint arrays");
}
}
}
for (int i = 0; i < nA; ++i)
{
for (int j = 0; j < nB; ++j)
{
if (U[std::max(A[i], B[j])][std::min(A[i], B[j])] == 1)
{
return true;
}
}
}
return false;
}
int main()
{
assert(1 == scanf("%d", &C));
int maximumCalls = 0;
for (int c = 0; c < C; ++c)
{
call_counter = 0;
assert(2 == scanf("%d %d", &N, &D));
present.assign(N, false);
U.resize(N);
for (int i = 1; i < N; ++i)
{
U[i].resize(i);
for (int j = 0; j < i; ++j)
{
assert(1 == scanf("%d", &U[i][j]));
}
}
for (int i = 2; i < N; ++i)
{
for (int j = 1; j < i; ++j)
{
for (int k = 0; k < j; ++k)
{
if (U[i][j] + U[i][k] + U[j][k] < D)
{
printf("Insufficient Density\n");
exit(0);
}
}
}
}
std::vector<int> t = longest_trip(N, D);
int l = t.size();
printf("%d\n", l);
for (int i = 0; i < l; ++i)
{
printf(i == 0 ? "%d" : " %d", t[i]);
}
printf("\n");
printf("%d chiamate\n", call_counter);
maximumCalls = std::max(maximumCalls, call_counter);
call_counter = 0;
}
printf("%d max chiamate\n", maximumCalls);
return 0;
}
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
invalid array |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
invalid array |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
invalid array |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
invalid array |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
invalid array |
| 2 |
Halted |
0 ms |
0 KB |
- |
