oj.uz

Submission #971275

# Submission time Handle Problem Language Result Execution time Memory
971275 2024-04-28T09:35:52 Z aryanc403 Cave (IOI13_cave) C++17
100 / 100
 1480 ms 860 KB 
#include "cave.h"

/*
  Compete against Yourself.
  Author - Aryan (@aryanc403)
*/
/*
  Credits -
  Atcoder library - https://atcoder.github.io/ac-library/production/document_en/ (namespace atcoder)
  Github source code of library - https://github.com/atcoder/ac-library/tree/master/atcoder
  https://codeforces.com/contest/4/submission/150120627
*/

#ifdef ARYANC403
    #include <header.h>
#else
    #pragma GCC optimize ("Ofast")
    // #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
    #pragma GCC target ("sse,sse2,mmx")
    #pragma GCC optimize ("-ffloat-store")
    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    #define dbg(args...) 42;
    #define endl "\n"
#endif

// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
    Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define eb emplace_back
#define X first
#define Y second

using lli = int;
using mytype = long double;
using ii = pair<lli,lli>;
using vii = vector<ii>;
using vi = vector<lli>;

template <class T>
using ordered_set =  __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
// X.find_by_order(k) return kth element. 0 indexed.
// X.order_of_key(k) returns count of elements strictly less than k.

// namespace Re = std::ranges;
// namespace Ve = std::ranges::views;

const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
}

int tryCombination(int S[]);
void answer(int S[], int D[]);

void exploreCave(const lli N){
    int S[N],D[N];
    for(lli j=0;j<N;j++){
        S[j]=0;
        D[j]=-1;
    }

    set<lli> rem;
    for(lli j=0;j<N;j++)
        rem.insert(j);

    auto getIdx=[&](const lli idx)->ii{
        bool def = 0;
        auto chk=[&](const lli mid)->bool{
            for(const auto &j:rem)
                S[j]=!def;

            for(const auto &j:rem){
                if(j>mid)
                    break;
                S[j]=def;
            }

            const lli dr = tryCombination(S);
            return dr==-1||dr>idx;
        };

        if(!chk(N))
            def=1;

        lli l=-1,r=N;
        while(r-l>1){
            const lli mid = (l+r)/2;
            if(chk(mid))
                r=mid;
            else
                l=mid;
        }
        // dbg(idx,r,def);
        return {r,def};
    };

    for(lli j=0;j<N;j++){
        const auto resp = getIdx(j);
        D[resp.X]=j;
        S[resp.X]=resp.Y;
        rem.erase(resp.X);
    }

    // dbg("ans",prt(N,S));
    // dbg("ans",prt(N,D));
    answer(S,D);
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 712 KB Output is correct
2 Correct 567 ms 716 KB Output is correct
3 Correct 865 ms 776 KB Output is correct
4 Correct 602 ms 720 KB Output is correct
5 Correct 882 ms 776 KB Output is correct
6 Correct 846 ms 848 KB Output is correct
7 Correct 860 ms 852 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 856 ms 776 KB Output is correct
13 Correct 879 ms 772 KB Output is correct
14 Correct 841 ms 780 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 863 ms 772 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1210 ms 860 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 860 ms 776 KB Output is correct
7 Correct 1459 ms 776 KB Output is correct
8 Correct 1399 ms 776 KB Output is correct
9 Correct 1422 ms 772 KB Output is correct
10 Correct 1415 ms 776 KB Output is correct
11 Correct 1480 ms 776 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Correct 0 ms 440 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Correct 0 ms 440 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 203 ms 596 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 178 ms 564 KB Output is correct
24 Correct 177 ms 348 KB Output is correct
25 Correct 182 ms 596 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 128 ms 568 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 203 ms 564 KB Output is correct
31 Correct 202 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 178 ms 560 KB Output is correct
36 Correct 186 ms 600 KB Output is correct
37 Correct 0 ms 348 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 712 KB Output is correct
2 Correct 567 ms 716 KB Output is correct
3 Correct 865 ms 776 KB Output is correct
4 Correct 602 ms 720 KB Output is correct
5 Correct 882 ms 776 KB Output is correct
6 Correct 846 ms 848 KB Output is correct
7 Correct 860 ms 852 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 856 ms 776 KB Output is correct
13 Correct 879 ms 772 KB Output is correct
14 Correct 841 ms 780 KB Output is correct
15 Correct 863 ms 772 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1210 ms 860 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 860 ms 776 KB Output is correct
21 Correct 1459 ms 776 KB Output is correct
22 Correct 1399 ms 776 KB Output is correct
23 Correct 1422 ms 772 KB Output is correct
24 Correct 1415 ms 776 KB Output is correct
25 Correct 1480 ms 776 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 ms 436 KB Output is correct
28 Correct 0 ms 440 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 344 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 0 ms 344 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 1 ms 348 KB Output is correct
45 Correct 203 ms 596 KB Output is correct
46 Correct 1 ms 348 KB Output is correct
47 Correct 1 ms 348 KB Output is correct
48 Correct 178 ms 564 KB Output is correct
49 Correct 177 ms 348 KB Output is correct
50 Correct 182 ms 596 KB Output is correct
51 Correct 1 ms 348 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 128 ms 568 KB Output is correct
54 Correct 1 ms 348 KB Output is correct
55 Correct 203 ms 564 KB Output is correct
56 Correct 202 ms 348 KB Output is correct
57 Correct 1 ms 348 KB Output is correct
58 Correct 1 ms 348 KB Output is correct
59 Correct 1 ms 348 KB Output is correct
60 Correct 178 ms 560 KB Output is correct
61 Correct 186 ms 600 KB Output is correct
62 Correct 0 ms 348 KB Output is correct
63 Correct 556 ms 716 KB Output is correct
64 Correct 562 ms 712 KB Output is correct
65 Correct 873 ms 776 KB Output is correct
66 Correct 594 ms 720 KB Output is correct
67 Correct 892 ms 772 KB Output is correct
68 Correct 846 ms 600 KB Output is correct
69 Correct 865 ms 776 KB Output is correct
70 Correct 0 ms 344 KB Output is correct
71 Correct 1 ms 348 KB Output is correct
72 Correct 835 ms 804 KB Output is correct
73 Correct 856 ms 604 KB Output is correct
74 Correct 847 ms 772 KB Output is correct
75 Correct 1211 ms 604 KB Output is correct
76 Correct 1 ms 436 KB Output is correct
77 Correct 1 ms 348 KB Output is correct
78 Correct 879 ms 772 KB Output is correct
79 Correct 1471 ms 856 KB Output is correct
80 Correct 1422 ms 776 KB Output is correct
81 Correct 1383 ms 776 KB Output is correct
82 Correct 1404 ms 776 KB Output is correct
83 Correct 1479 ms 780 KB Output is correct
84 Correct 1 ms 348 KB Output is correct
85 Correct 204 ms 576 KB Output is correct
86 Correct 1459 ms 780 KB Output is correct
87 Correct 1 ms 344 KB Output is correct
88 Correct 1 ms 344 KB Output is correct
89 Correct 179 ms 564 KB Output is correct
90 Correct 178 ms 564 KB Output is correct
91 Correct 178 ms 344 KB Output is correct
92 Correct 1389 ms 776 KB Output is correct
93 Correct 1400 ms 776 KB Output is correct
94 Correct 1396 ms 848 KB Output is correct
95 Correct 1 ms 436 KB Output is correct
96 Correct 1 ms 348 KB Output is correct
97 Correct 1207 ms 776 KB Output is correct
98 Correct 125 ms 560 KB Output is correct
99 Correct 845 ms 604 KB Output is correct
100 Correct 1 ms 348 KB Output is correct
101 Correct 202 ms 564 KB Output is correct
102 Correct 203 ms 344 KB Output is correct
103 Correct 1424 ms 792 KB Output is correct
104 Correct 1 ms 348 KB Output is correct
105 Correct 1 ms 348 KB Output is correct
106 Correct 1 ms 348 KB Output is correct
107 Correct 182 ms 564 KB Output is correct
108 Correct 178 ms 564 KB Output is correct
109 Correct 1426 ms 776 KB Output is correct
110 Correct 1405 ms 776 KB Output is correct
111 Correct 0 ms 344 KB Output is correct