Submission #659046

#	Time	Username	Problem	Language	Result	Execution time	Memory
659046		colazcy	Sob (COCI19_sob)	C++17	39 / 110	123 ms	9992 KiB

sob

#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){
    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].push_back(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::freopen("match.in","r",stdin);
    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 (stderr)

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 / 10
• Subtask 2: 29 / 29
• Subtask 3: 0 / 39
• Subtask 4: 0 / 32