oj.uz

Submission #659047

# Submission time Handle Problem Language Result Execution time Memory
659047 2022-11-16T06:33:10 Z colazcy Sob (COCI19_sob) C++17
78 / 110
 123 ms 10016 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{
        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

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.0 / 10.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 123 ms 9972 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 122 ms 10016 KB Output is correct
7 Correct 53 ms 4940 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 0 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 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #4
0 / 32.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 123 ms 9972 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 122 ms 10016 KB Output is correct
11 Correct 53 ms 4940 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 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 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 23 ms 2252 KB Output is correct
20 Runtime error 11 ms 9812 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -