oj.uz

Submission #659046

# Submission time Handle Problem Language Result Execution time Memory
659046 2022-11-16T06:19:32 Z colazcy Sob (COCI19_sob) C++17
39 / 110
 123 ms 9992 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){
    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

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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 118 ms 9980 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 0 ms 220 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 220 KB Output is correct
5 Correct 1 ms 220 KB Output is correct
6 Correct 123 ms 9992 KB Output is correct
7 Correct 55 ms 4944 KB Output is correct

Subtask #3
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 1 ms 284 KB Output is correct
4 Runtime error 1 ms 472 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 118 ms 9980 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 0 ms 220 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 220 KB Output is correct
9 Correct 1 ms 220 KB Output is correct
10 Correct 123 ms 9992 KB Output is correct
11 Correct 55 ms 4944 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 284 KB Output is correct
15 Runtime error 1 ms 472 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -