oj.uz

Submission #847741

# Submission time Handle Problem Language Result Execution time Memory
847741 2023-09-10T09:54:27 Z MrBrionix Longest Trip (IOI23_longesttrip) C++17
85 / 100
 14 ms 1228 KB 
#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();
}

bool comp(pair<int,vector<int>> &a,pair<int,vector<int>> &b){
    return a.first<b.first;
}

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)
{
    deque<vector<int>> q,succ;
    deque<pair<vector<int>,vector<int>>> q2;
    
    
    for(int i=0;i<N;i++){
        q.push_back({i});
    }
    shuffle(q.begin(),q.end(),rng);
    
    
    while(q.size()>=5){
        succ.clear();
        while(q.size()>=2){
            auto a = q.front();
            q.pop_front();
            auto b = q.front();
            q.pop_front();
            
            if(are_connected({*a.begin()},{*b.begin()})){
                add(a,b);
                succ.push_back(a);
            }else{
                q2.push_back({a,b});
            }
        }
        if(q.size()==1)succ.push_back(q[0]);
        
        while(q2.size()>=2){
            auto a = q2.front().first;
            auto b = q2.front().second;
            q2.pop_front();
            
            auto c = q2.front().first;
            auto d = q2.front().second;
            q2.pop_front();
            
            if(!are_connected({*a.begin()},{*c.begin()})){
                add(c,b);
                add(a,d);
                succ.push_back(a);
                succ.push_back(c);
            }else if(!are_connected({*b.begin()},{*d.begin()})){
                add(c,b);
                add(a,d);
                succ.push_back(a);
                succ.push_back(c);
            }else{
                add(a,c);
                add(b,d);
                succ.push_back(a);
                succ.push_back(b);
            }
        }
        if(q2.size()==1){
            succ.push_back(q2[0].first);
            succ.push_back(q2[0].second);
        }
        q2.clear();
        q.clear();
        q=succ;
    }
    
    while(q.size()>2){
        auto a = q.front();
        q.pop_front();
        auto b = q.front();
        q.pop_front();
        auto c = q.front();
        q.pop_front();
        
        if(are_connected({*a.begin()},{*b.begin()})){
        }else if(are_connected({*a.begin()},{*c.begin()})){
            swap(b,c);
        }else{
            swap(a,c);
        }
        
        add(a,b);
        q.push_back(a);
        q.push_front(c);
    }

    //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) ? vector<int>{l1} : vector<int>{l1,r1},(l2 == r2) ? vector<int>{l2} : vector<int>{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;
  }
 */

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 608 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 344 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 5 ms 608 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 6 ms 600 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 11 ms 344 KB Output is correct
7 Correct 6 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 5 ms 460 KB Output is correct
11 Correct 5 ms 716 KB Output is correct
12 Correct 5 ms 608 KB Output is correct
13 Correct 6 ms 612 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 344 KB Output is correct
2 Correct 8 ms 344 KB Output is correct
3 Correct 5 ms 600 KB Output is correct
4 Correct 5 ms 600 KB Output is correct
5 Correct 5 ms 856 KB Output is correct
6 Correct 11 ms 596 KB Output is correct
7 Correct 6 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 5 ms 720 KB Output is correct
11 Correct 5 ms 608 KB Output is correct
12 Correct 5 ms 716 KB Output is correct
13 Correct 6 ms 600 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 8 ms 344 KB Output is correct
16 Correct 8 ms 344 KB Output is correct
17 Correct 6 ms 600 KB Output is correct
18 Correct 6 ms 344 KB Output is correct
19 Correct 6 ms 856 KB Output is correct
20 Correct 6 ms 1012 KB Output is correct
21 Correct 7 ms 632 KB Output is correct
22 Correct 7 ms 612 KB Output is correct
23 Correct 6 ms 980 KB Output is correct
24 Correct 5 ms 724 KB Output is correct
25 Correct 9 ms 344 KB Output is correct
26 Correct 6 ms 344 KB Output is correct
27 Correct 7 ms 344 KB Output is correct
28 Correct 8 ms 344 KB Output is correct
29 Correct 8 ms 344 KB Output is correct
30 Correct 5 ms 444 KB Output is correct
31 Correct 6 ms 444 KB Output is correct
32 Correct 7 ms 448 KB Output is correct
33 Correct 5 ms 596 KB Output is correct
34 Correct 5 ms 344 KB Output is correct
35 Correct 5 ms 344 KB Output is correct
36 Correct 5 ms 712 KB Output is correct
37 Correct 6 ms 720 KB Output is correct
38 Correct 5 ms 468 KB Output is correct
39 Correct 6 ms 864 KB Output is correct
40 Correct 7 ms 716 KB Output is correct
41 Correct 7 ms 608 KB Output is correct
42 Correct 7 ms 608 KB Output is correct
43 Correct 7 ms 868 KB Output is correct
44 Correct 7 ms 872 KB Output is correct
45 Correct 14 ms 344 KB Output is correct
46 Correct 10 ms 344 KB Output is correct
47 Correct 8 ms 344 KB Output is correct
48 Correct 10 ms 344 KB Output is correct
49 Correct 11 ms 344 KB Output is correct
50 Correct 6 ms 452 KB Output is correct
51 Correct 7 ms 448 KB Output is correct
52 Correct 8 ms 696 KB Output is correct
53 Correct 6 ms 344 KB Output is correct
54 Correct 6 ms 340 KB Output is correct
55 Correct 6 ms 796 KB Output is correct
56 Correct 6 ms 728 KB Output is correct
57 Correct 6 ms 624 KB Output is correct
58 Correct 6 ms 876 KB Output is correct
59 Correct 8 ms 976 KB Output is correct
60 Correct 7 ms 976 KB Output is correct
61 Correct 8 ms 868 KB Output is correct
62 Correct 8 ms 600 KB Output is correct
63 Correct 8 ms 724 KB Output is correct
64 Correct 8 ms 860 KB Output is correct

Subtask #4
45.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 9 ms 344 KB Output is correct
8 Correct 5 ms 340 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 5 ms 716 KB Output is correct
11 Correct 5 ms 624 KB Output is correct
12 Correct 5 ms 860 KB Output is correct
13 Correct 5 ms 608 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 8 ms 344 KB Output is correct
16 Correct 8 ms 344 KB Output is correct
17 Correct 8 ms 344 KB Output is correct
18 Correct 6 ms 600 KB Output is correct
19 Correct 6 ms 852 KB Output is correct
20 Correct 7 ms 712 KB Output is correct
21 Correct 7 ms 340 KB Output is correct
22 Correct 7 ms 344 KB Output is correct
23 Correct 6 ms 344 KB Output is correct
24 Correct 6 ms 344 KB Output is correct
25 Correct 6 ms 344 KB Output is correct
26 Correct 5 ms 440 KB Output is correct
27 Correct 6 ms 444 KB Output is correct
28 Correct 8 ms 600 KB Output is correct
29 Correct 5 ms 344 KB Output is correct
30 Correct 5 ms 344 KB Output is correct
31 Correct 5 ms 600 KB Output is correct
32 Correct 11 ms 344 KB Output is correct
33 Correct 9 ms 344 KB Output is correct
34 Correct 8 ms 344 KB Output is correct
35 Correct 9 ms 344 KB Output is correct
36 Correct 10 ms 344 KB Output is correct
37 Correct 5 ms 700 KB Output is correct
38 Correct 7 ms 440 KB Output is correct
39 Correct 7 ms 956 KB Output is correct
40 Correct 5 ms 600 KB Output is correct
41 Correct 6 ms 344 KB Output is correct
42 Correct 6 ms 344 KB Output is correct
43 Correct 7 ms 1228 KB Output is correct
44 Correct 5 ms 728 KB Output is correct
45 Correct 6 ms 860 KB Output is correct
46 Correct 6 ms 980 KB Output is correct
47 Correct 5 ms 708 KB Output is correct
48 Correct 5 ms 608 KB Output is correct
49 Correct 5 ms 500 KB Output is correct
50 Correct 7 ms 600 KB Output is correct
51 Correct 6 ms 472 KB Output is correct
52 Correct 9 ms 720 KB Output is correct
53 Correct 8 ms 712 KB Output is correct
54 Correct 7 ms 732 KB Output is correct
55 Correct 7 ms 616 KB Output is correct
56 Correct 5 ms 472 KB Output is correct
57 Correct 6 ms 864 KB Output is correct
58 Correct 6 ms 856 KB Output is correct
59 Correct 7 ms 472 KB Output is correct
60 Partially correct 7 ms 720 KB Output is partially correct
61 Correct 9 ms 716 KB Output is correct
62 Correct 5 ms 468 KB Output is correct
63 Correct 6 ms 724 KB Output is correct
64 Correct 10 ms 976 KB Output is correct
65 Correct 8 ms 872 KB Output is correct
66 Correct 9 ms 868 KB Output is correct
67 Partially correct 9 ms 616 KB Output is partially correct
68 Partially correct 8 ms 868 KB Output is partially correct
69 Correct 12 ms 868 KB Output is correct
70 Correct 9 ms 868 KB Output is correct
71 Correct 6 ms 872 KB Output is correct
72 Correct 7 ms 976 KB Output is correct
73 Correct 8 ms 856 KB Output is correct
74 Partially correct 7 ms 728 KB Output is partially correct
75 Partially correct 10 ms 860 KB Output is partially correct
76 Correct 8 ms 1120 KB Output is correct
77 Correct 7 ms 1212 KB Output is correct
78 Correct 6 ms 724 KB Output is correct
79 Correct 7 ms 980 KB Output is correct
80 Correct 8 ms 620 KB Output is correct
81 Correct 7 ms 868 KB Output is correct
82 Partially correct 8 ms 1228 KB Output is partially correct