Submission #659047

#	Time	Username	Problem	Language	Result	Execution time	Memory
659047		colazcy	Sob (COCI19_sob)	C++17	78 / 110	123 ms	10016 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{
        for(auto it = vb[1].begin();it != vb[1].end();it++)
            if(chk(va[0].back(),*it)){
                ans(va[0].back(),*it);
                va[0].pop_back();
                vb[1].erase(it);
                break;
            }
        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 (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 29 / 29
• Subtask 3: 39 / 39
• Subtask 4: 0 / 32