oj.uz

Submission #910211

# Submission time Handle Problem Language Result Execution time Memory
910211 2024-01-18T01:59:59 Z biank Longest Trip (IOI23_longesttrip) C++17
85 / 100
 13 ms 1136 KB 
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define SIZE(x) (int)x.size()
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define pb push_back
typedef vector<int> vi;
bool are_connected(vi A, vi B);

vi longest_trip(int N, int D) {
    (void)D;
    queue<vi> q;
    forn(i,N) q.push({i});
    auto plop = [&](){
      vi x = q.front();
      q.pop();
      return x;  
    };
    while(SIZE(q)>=3) {
        vi a = plop(),
           b = plop(),
           c = plop();
        if(are_connected({a.back()},{b.front()})) {
            forn(i,SIZE(b)) a.pb(b[i]);
            q.push(a), q.push(c);
        } else if(are_connected({a.back()},{c.front()})) {
            forn(i,SIZE(c)) a.pb(c[i]);
            q.push(a), q.push(b);
        } else {
            reverse(ALL(b));
            forn(i,SIZE(c)) b.pb(c[i]);
            q.push(b), q.push(a);
        }
    }
    vi a = plop(), b = plop();
    if(SIZE(b)>SIZE(a)) swap(a,b);
    if(b.empty() || !are_connected(a,b)) return a;
    
    vi qa = {a.front()};
    if(a.back() != qa.back()) qa.pb(a.back());
    vi qb = {b.front()};
    if(b.back() != qb.back()) qb.pb(b.back());
    
    if(are_connected(qa, qb)) {
        if(are_connected({a.back()}, {b.front()})) {
            forn(i,SIZE(b)) a.pb(b[i]);
            return a;
        }
        
        if(are_connected({b.back()}, {a.front()})) {
            forn(i,SIZE(a)) b.pb(a[i]);
            return b;
        }
        
        if(are_connected({a.front()},{b.front()})) {
            reverse(ALL(a));
            forn(i,SIZE(b)) a.pb(b[i]);
            return a;
        }
        
        if(are_connected({a.back()}, {b.back()})) {
            reverse(ALL(b));
            forn(i,SIZE(b)) a.pb(b[i]);
            return a;
        }
        
    }
    
    int l=0, r=SIZE(a);
    while(l+1<r) {
        int m=(l+r)/2;
        if(are_connected(b,vi(a.begin()+m,a.begin()+r))) l=m;
        else r=m;
    }
    
    int i=l;
    
    l=0, r=SIZE(b);
    while(l+1<r) {
        int m=(l+r)/2;
        if(are_connected({a[i]},vi(b.begin()+m,b.begin()+r))) l=m;
        else r=m;
    }
    
    int j=l;
    
    vi ans;
    forsn(p,j+1,SIZE(b)) ans.pb(b[p]);
    forn(p,j+1) ans.pb(b[p]);
    forsn(p,i,SIZE(a)) ans.pb(a[p]);
    forn(p,i) ans.pb(a[p]);
    
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 8 ms 344 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 7 ms 456 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 6 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 8 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 6 ms 604 KB Output is correct
10 Correct 5 ms 608 KB Output is correct
11 Correct 6 ms 608 KB Output is correct
12 Correct 5 ms 456 KB Output is correct
13 Correct 6 ms 608 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 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 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 7 ms 344 KB Output is correct
8 Correct 6 ms 600 KB Output is correct
9 Correct 6 ms 856 KB Output is correct
10 Correct 5 ms 460 KB Output is correct
11 Correct 5 ms 460 KB Output is correct
12 Correct 5 ms 608 KB Output is correct
13 Correct 5 ms 608 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 7 ms 344 KB Output is correct
16 Correct 8 ms 344 KB Output is correct
17 Correct 7 ms 344 KB Output is correct
18 Correct 7 ms 344 KB Output is correct
19 Correct 6 ms 700 KB Output is correct
20 Correct 5 ms 600 KB Output is correct
21 Correct 6 ms 864 KB Output is correct
22 Correct 6 ms 624 KB Output is correct
23 Correct 5 ms 716 KB Output is correct
24 Correct 5 ms 976 KB Output is correct
25 Correct 6 ms 352 KB Output is correct
26 Correct 9 ms 344 KB Output is correct
27 Correct 5 ms 344 KB Output is correct
28 Correct 5 ms 600 KB Output is correct
29 Correct 6 ms 344 KB Output is correct
30 Correct 5 ms 612 KB Output is correct
31 Correct 7 ms 440 KB Output is correct
32 Correct 7 ms 444 KB Output is correct
33 Correct 5 ms 600 KB Output is correct
34 Correct 5 ms 684 KB Output is correct
35 Correct 6 ms 600 KB Output is correct
36 Correct 5 ms 624 KB Output is correct
37 Correct 6 ms 868 KB Output is correct
38 Correct 6 ms 720 KB Output is correct
39 Correct 6 ms 864 KB Output is correct
40 Correct 7 ms 864 KB Output is correct
41 Correct 7 ms 612 KB Output is correct
42 Correct 7 ms 608 KB Output is correct
43 Correct 8 ms 464 KB Output is correct
44 Correct 8 ms 1120 KB Output is correct
45 Correct 10 ms 344 KB Output is correct
46 Correct 10 ms 344 KB Output is correct
47 Correct 7 ms 344 KB Output is correct
48 Correct 8 ms 344 KB Output is correct
49 Correct 7 ms 344 KB Output is correct
50 Correct 5 ms 696 KB Output is correct
51 Correct 9 ms 436 KB Output is correct
52 Correct 8 ms 444 KB Output is correct
53 Correct 5 ms 600 KB Output is correct
54 Correct 6 ms 856 KB Output is correct
55 Correct 7 ms 604 KB Output is correct
56 Correct 5 ms 468 KB Output is correct
57 Correct 6 ms 720 KB Output is correct
58 Correct 7 ms 1124 KB Output is correct
59 Correct 7 ms 868 KB Output is correct
60 Correct 8 ms 868 KB Output is correct
61 Correct 8 ms 720 KB Output is correct
62 Correct 8 ms 856 KB Output is correct
63 Correct 8 ms 864 KB Output is correct
64 Correct 7 ms 608 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 608 KB Output is correct
6 Correct 13 ms 344 KB Output is correct
7 Correct 7 ms 344 KB Output is correct
8 Correct 5 ms 600 KB Output is correct
9 Correct 5 ms 600 KB Output is correct
10 Correct 6 ms 608 KB Output is correct
11 Correct 6 ms 460 KB Output is correct
12 Correct 5 ms 600 KB Output is correct
13 Correct 5 ms 704 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 7 ms 344 KB Output is correct
16 Correct 7 ms 344 KB Output is correct
17 Correct 7 ms 344 KB Output is correct
18 Correct 6 ms 344 KB Output is correct
19 Correct 7 ms 600 KB Output is correct
20 Correct 6 ms 600 KB Output is correct
21 Correct 6 ms 344 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 340 KB Output is correct
26 Correct 6 ms 440 KB Output is correct
27 Correct 7 ms 440 KB Output is correct
28 Correct 7 ms 440 KB Output is correct
29 Correct 5 ms 344 KB Output is correct
30 Correct 5 ms 600 KB Output is correct
31 Correct 5 ms 600 KB Output is correct
32 Correct 10 ms 344 KB Output is correct
33 Correct 9 ms 344 KB Output is correct
34 Correct 11 ms 344 KB Output is correct
35 Correct 8 ms 352 KB Output is correct
36 Correct 10 ms 344 KB Output is correct
37 Correct 6 ms 440 KB Output is correct
38 Correct 7 ms 432 KB Output is correct
39 Correct 8 ms 440 KB Output is correct
40 Correct 5 ms 344 KB Output is correct
41 Correct 6 ms 600 KB Output is correct
42 Correct 6 ms 600 KB Output is correct
43 Correct 5 ms 716 KB Output is correct
44 Correct 7 ms 968 KB Output is correct
45 Correct 7 ms 716 KB Output is correct
46 Correct 5 ms 728 KB Output is correct
47 Correct 6 ms 716 KB Output is correct
48 Correct 7 ms 464 KB Output is correct
49 Correct 7 ms 868 KB Output is correct
50 Partially correct 7 ms 724 KB Output is partially correct
51 Partially correct 8 ms 728 KB Output is partially correct
52 Partially correct 8 ms 724 KB Output is partially correct
53 Partially correct 7 ms 464 KB Output is partially correct
54 Partially correct 8 ms 720 KB Output is partially correct
55 Partially correct 8 ms 720 KB Output is partially correct
56 Correct 7 ms 612 KB Output is correct
57 Correct 7 ms 720 KB Output is correct
58 Partially correct 9 ms 472 KB Output is partially correct
59 Partially correct 8 ms 880 KB Output is partially correct
60 Partially correct 8 ms 696 KB Output is partially correct
61 Partially correct 7 ms 728 KB Output is partially correct
62 Correct 6 ms 464 KB Output is correct
63 Correct 6 ms 1136 KB Output is correct
64 Correct 9 ms 640 KB Output is correct
65 Partially correct 8 ms 740 KB Output is partially correct
66 Partially correct 8 ms 732 KB Output is partially correct
67 Partially correct 8 ms 728 KB Output is partially correct
68 Partially correct 8 ms 480 KB Output is partially correct
69 Partially correct 9 ms 612 KB Output is partially correct
70 Partially correct 9 ms 728 KB Output is partially correct
71 Correct 7 ms 872 KB Output is correct
72 Correct 8 ms 880 KB Output is correct
73 Partially correct 9 ms 876 KB Output is partially correct
74 Partially correct 9 ms 484 KB Output is partially correct
75 Partially correct 10 ms 972 KB Output is partially correct
76 Partially correct 9 ms 632 KB Output is partially correct
77 Correct 7 ms 972 KB Output is correct
78 Correct 8 ms 968 KB Output is correct
79 Partially correct 8 ms 972 KB Output is partially correct
80 Partially correct 10 ms 600 KB Output is partially correct
81 Partially correct 9 ms 600 KB Output is partially correct
82 Partially correct 8 ms 852 KB Output is partially correct