oj.uz

Submission #379531

# Submission time Handle Problem Language Result Execution time Memory
379531 2021-03-18T12:48:30 Z bibabas Sob (COCI19_sob) C++14
110 / 110
 153 ms 21720 KB 
// #define _FORTIFY_SOURCE 0 
// #pragma GCC optimize("Ofast") 
// #pragma GCC optimize("no-stack-protector") 
// #pragma GCC optimize("unroll-loops") 
// //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native") 
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx") 
// #pragma GCC optimize("inline") 
// #pragma GCC optimize("-fgcse") 
// #pragma GCC optimize("-fgcse-lm") 
// #pragma GCC optimize("-fipa-sra") 
// #pragma GCC optimize("-ftree-pre") 
// #pragma GCC optimize("-ftree-vrp") 
// #pragma GCC optimize("-fpeephole2") 
// #pragma GCC optimize("-ffast-math") 
// #pragma GCC optimize("-fsched-spec") 
// #pragma GCC optimize("unroll-loops") 
// #pragma GCC optimize("-falign-jumps") 
// #pragma GCC optimize("-falign-loops") 
// #pragma GCC optimize("-falign-labels") 
// #pragma GCC optimize("-fdevirtualize") 
// #pragma GCC optimize("-fcaller-saves") 
// #pragma GCC optimize("-fcrossjumping") 
// #pragma GCC optimize("-fthread-jumps") 
// #pragma GCC optimize("-funroll-loops") 
// #pragma GCC optimize("-fwhole-program") 
// #pragma GCC optimize("-freorder-blocks") 
// #pragma GCC optimize("-fschedule-insns") 
// #pragma GCC optimize("inline-functions") 
// #pragma GCC optimize("-ftree-tail-merge") 
// #pragma GCC optimize("-fschedule-insns2") 
// #pragma GCC optimize("-fstrict-aliasing") 
// #pragma GCC optimize("-fstrict-overflow") 
// #pragma GCC optimize("-falign-functions") 
// #pragma GCC optimize("-fcse-skip-blocks") 
// #pragma GCC optimize("-fcse-follow-jumps") 
// #pragma GCC optimize("-fsched-interblock") 
// #pragma GCC optimize("-fpartial-inlining") 
// #pragma GCC optimize("no-stack-protector") 
// #pragma GCC optimize("-freorder-functions") 
// #pragma GCC optimize("-findirect-inlining") 
// #pragma GCC optimize("-fhoist-adjacent-loads") 
// #pragma GCC optimize("-frerun-cse-after-loop") 
// #pragma GCC optimize("inline-small-functions") 
// #pragma GCC optimize("-finline-small-functions") 
// #pragma GCC optimize("-ftree-switch-conversion") 
// #pragma GCC optimize("-foptimize-sibling-calls") 
// #pragma GCC optimize("-fexpensive-optimizations") 
// #pragma GCC optimize("-funsafe-loop-optimizations") 
// #pragma GCC optimize("inline-functions-called-once") 
// #pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>

using namespace std;
         
#define ll long long
#define ull unsigned ll
#define vi vector<ll>
#define vvi vector<vi>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define ld long double
#define pii pair<ll, ll>
#define mt make_tuple
#define mn(a, b) a = min(a, b)
#define mx(a, b) a = max(a, b)
#define base complex<ld>
 
using namespace std;
const ll INF = (ll)2e9;
const ll inf = (ll)1e18;
const ld eps = (ld)1e-12;
const ll mod = (ll)1e9 + 7;
const ll p = 31;
const ll mod2 = (ll)1e9 + 7;
const ll MAXN = (ll)1000 + 3;
const ll MAXC = (ll)1e6 + 11;
const ll MAXE = (ll)100;
const ll MAXLOG = (ll)19;
const ll asci = (ll)256;
const ll block = 31623;
const ld PI = acos(-1LL);
const ld e = 2.7182818284;
         
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<
// pii,
// null_type,
// less<pii>,
// rb_tree_tag,
// tree_order_statistics_node_update>
// ordered_set;

ll int_rand() {
    if (RAND_MAX == (1LL << 15) - 1LL) {
        return (rand() << 15) + rand();
    }
    return rand();
}

ll ll_rand() {
    return ((ll)int_rand() << 30LL) + int_rand();
}

istream& operator >>(istream &in, pii &x) {
    cin >> x.first >> x.second;
    return in;
}
         
template <class T>
istream& operator >>(istream &in, vector<T> &arr){
    for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
}

vector<pii> get_ans(int l, int r, int n) {
    if (n == 0) return {};
    int mod = 1;
    while (mod < n) mod <<= 1;
    vi used_l(mod, -1), used_r(mod, -1);
    for (int j = 0; j < n; ++j) {
        used_r[(r + j) & (mod - 1)] = j + r;
        used_l[(l + j) & (mod - 1)] = j + l;
    }
    vector<pii> ans;
    int nn = n;
    for (int i = 0; i < mod; ++i) {
        if (used_l[i] != -1 && used_r[i] != -1) 
        ans.push_back(mp(used_l[i], used_r[i])), --nn;
    }
    int ln = l, rn = r;
    for (; ln < l + n; ++ln) if (used_r[ln & (mod - 1)] == -1) break;
    for (; rn < r + n; ++rn) if (used_l[rn & (mod - 1)] == -1) break;
    for (auto x : get_ans(ln, rn, nn)) ans.push_back(x);
    return ans;
}

void solve() {
    int n, m; cin >> n >> m;
    auto ans = get_ans(0, m, n);
    sort(all(ans));
    for (auto x : ans) cout << x.first << " " << x.second << "\n";
}

signed main() {
    srand(time(0LL));
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr); 
#endif
    cout.precision(30);
    
    solve();

    return 0LL;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 63 ms 8676 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 63 ms 8676 KB Output is correct
7 Correct 42 ms 4964 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 63 ms 8676 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 63 ms 8676 KB Output is correct
11 Correct 42 ms 4964 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 21 ms 3048 KB Output is correct
20 Correct 58 ms 10592 KB Output is correct
21 Correct 3 ms 748 KB Output is correct
22 Correct 2 ms 620 KB Output is correct
23 Correct 82 ms 21720 KB Output is correct
24 Correct 153 ms 18396 KB Output is correct
25 Correct 121 ms 17628 KB Output is correct