This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (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);
| ~~~~~~~~~~^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |