oj.uz

Submission #911230

# Submission time Handle Problem Language Result Execution time Memory
911230 2024-01-18T16:26:58 Z biank Longest Trip (IOI23_longesttrip) C++17
100 / 100
 11 ms 864 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 dforn(i,n) for(int i=int(n)-1;i>=0;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);
int n;
const int MAXN = 256;
int c[MAXN][MAXN];

bool query(int x, int y) {
    if(c[x][y]==1) return true;
    if(c[x][y]==0) return false;
    forn(z,n) {
        if(z==x||z==y) continue;
        if(c[x][z]==0 && c[y][z]==0) {
            c[x][y]=c[y][x]=1;
            return true;
        }
    }
    c[x][y]=c[y][x]=are_connected({x},{y});
    return c[x][y]; 
}

int bs(vi a, vi b) {
    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;
    }
    return l;
}

vi longest_trip(int N, int D) {
    n=N;
    memset(c,-1,sizeof c);
    (void)D;
    vi P;
    forn(i,n) P.pb(i);
    srand(time(0));
    random_shuffle(ALL(P));
    vi a={P[0]}, b;
    forsn(i,1,n) {
        if(query(a.back(),P[i])) {
            a.pb(P[i]);
        } else if(!b.empty() && query(a.back(),b.back())) {
            dforn(j,SIZE(b)) a.pb(b[j]);
            b={P[i]};
        } else if(b.empty() || query(b.back(),P[i])) {
            b.pb(P[i]);
        }
    }
    if(SIZE(b)>SIZE(a)) swap(a,b);
    if(b.empty()||!are_connected(a,b)) return a;
    
    if(query(a.back(),b.front())) {
        forn(i,SIZE(b)) a.pb(b[i]);
        return a;
    } else if(query(b.back(),a.front())) {
        forn(i,SIZE(a)) b.pb(a[i]);
        return b;
    } else if(query(a.front(),b.front())) {
        reverse(ALL(a));
        forn(i,SIZE(b)) a.pb(b[i]);
        return a;
    } else if(query(a.back(),b.back())) {
        dforn(i,SIZE(b)) a.pb(b[i]);
        return a;
    }
    
    int i=bs(a,b);
    int j=bs(b,{a[i]});
    
    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 760 KB Output is correct
2 Correct 2 ms 600 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 600 KB Output is correct
2 Correct 5 ms 600 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 600 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 600 KB Output is correct
2 Correct 5 ms 600 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 600 KB Output is correct
6 Correct 10 ms 600 KB Output is correct
7 Correct 6 ms 600 KB Output is correct
8 Correct 5 ms 600 KB Output is correct
9 Correct 5 ms 856 KB Output is correct
10 Correct 5 ms 600 KB Output is correct
11 Correct 5 ms 600 KB Output is correct
12 Correct 5 ms 600 KB Output is correct
13 Correct 5 ms 600 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 600 KB Output is correct
2 Correct 7 ms 600 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 796 KB Output is correct
6 Correct 9 ms 600 KB Output is correct
7 Correct 6 ms 600 KB Output is correct
8 Correct 5 ms 596 KB Output is correct
9 Correct 5 ms 856 KB Output is correct
10 Correct 5 ms 600 KB Output is correct
11 Correct 6 ms 600 KB Output is correct
12 Correct 5 ms 600 KB Output is correct
13 Correct 5 ms 600 KB Output is correct
14 Correct 9 ms 600 KB Output is correct
15 Correct 10 ms 600 KB Output is correct
16 Correct 8 ms 600 KB Output is correct
17 Correct 7 ms 600 KB Output is correct
18 Correct 9 ms 600 KB Output is correct
19 Correct 6 ms 600 KB Output is correct
20 Correct 6 ms 600 KB Output is correct
21 Correct 7 ms 600 KB Output is correct
22 Correct 5 ms 600 KB Output is correct
23 Correct 5 ms 600 KB Output is correct
24 Correct 5 ms 600 KB Output is correct
25 Correct 8 ms 600 KB Output is correct
26 Correct 8 ms 600 KB Output is correct
27 Correct 6 ms 600 KB Output is correct
28 Correct 7 ms 600 KB Output is correct
29 Correct 7 ms 600 KB Output is correct
30 Correct 5 ms 600 KB Output is correct
31 Correct 6 ms 600 KB Output is correct
32 Correct 7 ms 600 KB Output is correct
33 Correct 5 ms 600 KB Output is correct
34 Correct 5 ms 600 KB Output is correct
35 Correct 5 ms 600 KB Output is correct
36 Correct 5 ms 600 KB Output is correct
37 Correct 6 ms 600 KB Output is correct
38 Correct 6 ms 600 KB Output is correct
39 Correct 6 ms 600 KB Output is correct
40 Correct 8 ms 852 KB Output is correct
41 Correct 6 ms 600 KB Output is correct
42 Correct 7 ms 600 KB Output is correct
43 Correct 6 ms 600 KB Output is correct
44 Correct 6 ms 600 KB Output is correct
45 Correct 9 ms 600 KB Output is correct
46 Correct 11 ms 600 KB Output is correct
47 Correct 9 ms 600 KB Output is correct
48 Correct 10 ms 600 KB Output is correct
49 Correct 7 ms 600 KB Output is correct
50 Correct 6 ms 600 KB Output is correct
51 Correct 6 ms 696 KB Output is correct
52 Correct 7 ms 696 KB Output is correct
53 Correct 6 ms 600 KB Output is correct
54 Correct 6 ms 600 KB Output is correct
55 Correct 7 ms 600 KB Output is correct
56 Correct 6 ms 600 KB Output is correct
57 Correct 5 ms 700 KB Output is correct
58 Correct 6 ms 704 KB Output is correct
59 Correct 6 ms 696 KB Output is correct
60 Correct 7 ms 700 KB Output is correct
61 Correct 7 ms 600 KB Output is correct
62 Correct 7 ms 716 KB Output is correct
63 Correct 8 ms 856 KB Output is correct
64 Correct 8 ms 856 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 596 KB Output is correct
2 Correct 5 ms 600 KB Output is correct
3 Correct 5 ms 600 KB Output is correct
4 Correct 5 ms 600 KB Output is correct
5 Correct 6 ms 600 KB Output is correct
6 Correct 11 ms 852 KB Output is correct
7 Correct 8 ms 600 KB Output is correct
8 Correct 6 ms 760 KB Output is correct
9 Correct 5 ms 600 KB Output is correct
10 Correct 5 ms 600 KB Output is correct
11 Correct 5 ms 600 KB Output is correct
12 Correct 5 ms 600 KB Output is correct
13 Correct 5 ms 600 KB Output is correct
14 Correct 8 ms 600 KB Output is correct
15 Correct 8 ms 600 KB Output is correct
16 Correct 9 ms 596 KB Output is correct
17 Correct 7 ms 600 KB Output is correct
18 Correct 7 ms 600 KB Output is correct
19 Correct 6 ms 600 KB Output is correct
20 Correct 6 ms 600 KB Output is correct
21 Correct 8 ms 600 KB Output is correct
22 Correct 8 ms 600 KB Output is correct
23 Correct 6 ms 600 KB Output is correct
24 Correct 6 ms 600 KB Output is correct
25 Correct 6 ms 600 KB Output is correct
26 Correct 5 ms 600 KB Output is correct
27 Correct 5 ms 600 KB Output is correct
28 Correct 6 ms 600 KB Output is correct
29 Correct 5 ms 856 KB Output is correct
30 Correct 6 ms 600 KB Output is correct
31 Correct 6 ms 600 KB Output is correct
32 Correct 9 ms 600 KB Output is correct
33 Correct 9 ms 600 KB Output is correct
34 Correct 7 ms 600 KB Output is correct
35 Correct 8 ms 852 KB Output is correct
36 Correct 7 ms 600 KB Output is correct
37 Correct 6 ms 600 KB Output is correct
38 Correct 7 ms 600 KB Output is correct
39 Correct 7 ms 692 KB Output is correct
40 Correct 5 ms 600 KB Output is correct
41 Correct 6 ms 600 KB Output is correct
42 Correct 6 ms 600 KB Output is correct
43 Correct 7 ms 600 KB Output is correct
44 Correct 6 ms 600 KB Output is correct
45 Correct 6 ms 600 KB Output is correct
46 Correct 6 ms 600 KB Output is correct
47 Correct 6 ms 600 KB Output is correct
48 Correct 5 ms 600 KB Output is correct
49 Correct 7 ms 600 KB Output is correct
50 Correct 6 ms 596 KB Output is correct
51 Correct 7 ms 600 KB Output is correct
52 Correct 7 ms 600 KB Output is correct
53 Correct 6 ms 600 KB Output is correct
54 Correct 7 ms 600 KB Output is correct
55 Correct 6 ms 600 KB Output is correct
56 Correct 7 ms 600 KB Output is correct
57 Correct 7 ms 596 KB Output is correct
58 Correct 8 ms 600 KB Output is correct
59 Correct 9 ms 600 KB Output is correct
60 Correct 7 ms 600 KB Output is correct
61 Correct 6 ms 600 KB Output is correct
62 Correct 5 ms 600 KB Output is correct
63 Correct 5 ms 704 KB Output is correct
64 Correct 7 ms 704 KB Output is correct
65 Correct 7 ms 700 KB Output is correct
66 Correct 7 ms 856 KB Output is correct
67 Correct 7 ms 600 KB Output is correct
68 Correct 7 ms 600 KB Output is correct
69 Correct 7 ms 856 KB Output is correct
70 Correct 8 ms 852 KB Output is correct
71 Correct 6 ms 864 KB Output is correct
72 Correct 7 ms 856 KB Output is correct
73 Correct 7 ms 856 KB Output is correct
74 Correct 7 ms 856 KB Output is correct
75 Correct 7 ms 600 KB Output is correct
76 Correct 7 ms 600 KB Output is correct
77 Correct 6 ms 696 KB Output is correct
78 Correct 7 ms 856 KB Output is correct
79 Correct 7 ms 856 KB Output is correct
80 Correct 7 ms 704 KB Output is correct
81 Correct 7 ms 600 KB Output is correct
82 Correct 8 ms 600 KB Output is correct