oj.uz

Submission #659049

# Submission time Handle Problem Language Result Execution time Memory
659049 2022-11-16T06:50:14 Z colazcy Sob (COCI19_sob) C++17
110 / 110
 235 ms 18948 KB 
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ci = const int;
constexpr int maxn = 1 << 20,inf = 0x3f3f3f3f;
constexpr bool test(ci x,ci p){return (x >> p) & 1;}
constexpr bool chk(ci x,ci y){return (x & y) == x;}

void ans(ci x,ci y){
    std::printf("%d %d\n",x,y);
    assert(chk(x,y));
}

void match(const std::vector<int> &A,const std::vector<int> &B,ci d = 0){
    assert(A.size() == B.size());
    if(A.empty())return;
    if(A.size() == 1)return ans(A.front(),B.front());
    std::vector<int> va[2],vb[2];
    va[0].reserve((A.size() + 1) >> 1);
    va[1].reserve((A.size() + 1) >> 1);
    vb[0].reserve((B.size() + 1) >> 1);
    vb[1].reserve((B.size() + 1) >> 1);
    for(let x : A)
        va[test(x,d)].push_back(x);
    for(let x : B)
        vb[test(x,d)].push_back(x);

    if(va[0].size() == vb[0].size()){
        match(va[0],vb[0],d + 1);
        match(va[1],vb[1],d + 1);
    }else{
        vb[0].insert(vb[0].begin(),vb[1].front());
        vb[1].erase(vb[1].begin());
        match(va[0],vb[0],d + 1);
        match(va[1],vb[1],d + 1);
    }
}

int n,m;
int main(){
    std::scanf("%d %d",&n,&m);
    std::vector<int> A,B;
    A.reserve(n);
    B.reserve(n);
    rep(i,0,n - 1)
        A.push_back(i),
        B.push_back(m + i);
    match(A,B);
    return 0;
}

Compilation message

sob.cpp: In function 'int main()':
sob.cpp:48:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     std::scanf("%d %d",&n,&m);
      |     ~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 125 ms 9976 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 124 ms 10028 KB Output is correct
7 Correct 56 ms 4812 KB Output is correct

Subtask #3
39.0 / 39.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 125 ms 9976 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 124 ms 10028 KB Output is correct
11 Correct 56 ms 4812 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 28 ms 2252 KB Output is correct
20 Correct 104 ms 7612 KB Output is correct
21 Correct 3 ms 544 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 135 ms 10740 KB Output is correct
24 Correct 235 ms 18948 KB Output is correct
25 Correct 228 ms 18684 KB Output is correct