oj.uz

답안 #770053

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
770053 2023-06-30T17:46:39 Z FatihSolak 앨리스, 밥, 서킷 (APIO23_abc) C++17
66 / 100
 461 ms 492868 KB 
#include "abc.h"
#include <bits/stdc++.h>
using namespace std;
#define K 16
#define M 20

// you may find the definitions useful
const int OP_ZERO    = 0;  // f(OP_ZERO,    x0, x1) = 0
const int OP_NOR     = 1;  // f(OP_NOR,     x0, x1) = !(x0 || x1)
const int OP_GREATER = 2;  // f(OP_GREATER, x0, x1) = (x0 > x1)
const int OP_NOT_X1  = 3;  // f(OP_NOT_X1,  x0, x1) = !x1
const int OP_LESS    = 4;  // f(OP_LESS,    x0, x1) = (x0 < x1)
const int OP_NOT_X0  = 5;  // f(OP_NOT_X0,  x0, x1) = !x0
const int OP_XOR     = 6;  // f(OP_XOR,     x0, x1) = (x0 ^ x1)
const int OP_NAND    = 7;  // f(OP_NAND,    x0, x1) = !(x0 && x1)
const int OP_AND     = 8;  // f(OP_AND,     x0, x1) = (x0 && x1)
const int OP_EQUAL   = 9;  // f(OP_EQUAL,   x0, x1) = (x0 == x1)
const int OP_X0      = 10; // f(OP_X0,      x0, x1) = x0
const int OP_GEQ     = 11; // f(OP_GEQ,     x0, x1) = (x0 >= x1)
const int OP_X1      = 12; // f(OP_X1,      x0, x1) = x1
const int OP_LEQ     = 13; // f(OP_LEQ,     x0, x1) = (x0 <= x1)
const int OP_OR      = 14; // f(OP_OR,      x0, x1) = (x0 || x1)
const int OP_ONE     = 15; // f(OP_ONE,     x0, x1) = 1


// Alice
int // returns la
alice(
    /*  in */ const int n,
    /*  in */ const char names[][5],
    /*  in */ const unsigned short numbers[],
    /* out */ bool outputs_alice[]
) {
    int ret = 0;
    for(int i = 0;i < n;i++){
        string t = names[i];
        for(int j = 0;j<t.size();j++){
            int num = t[j] - 'a' + 1;
            for(int c = 0;c<5;c++){
                if(num & (1<<c)){
                    outputs_alice[ret++] = 1;
                }
                else outputs_alice[ret++] = 0;
            }
        }
        for(int j = t.size();j<4;j++){
            for(int c = 0;c<5;c++){
                outputs_alice[ret++] = 0;
            }
        }
        for(int j = 0;j<K;j++){
            if(numbers[i] & (1<<j)){
                outputs_alice[ret++] = 1;
            }
            else outputs_alice[ret++] = 0;
        }
    }
    // int last = 0; 
    // for(int i = 0;i<n;i++){
    //     for(int j = 0;j<M;j++){
    //         cout << outputs_alice[last++] << ' ';
    //     }   
    //     cout << endl;
    //     for(int j = 0;j<K;j++){
    //         cout << outputs_alice[last++] << ' ';
    //     }   
    //     cout << endl;
    // }
    // cout << endl;
    return ret;
}


// Bob
int // returns lb
bob(
    /*  in */ const int m,
    /*  in */ const char senders[][5],
    /*  in */ const char recipients[][5],
    /* out */ bool outputs_bob[]
) {
    int ret = 0;
    for(int i = 0;i<m;i++){
        string t = senders[i];
        for(int j = 0;j<t.size();j++){
            int num = t[j] - 'a' + 1;
            for(int c = 0;c<5;c++){
                if(num & (1<<c)){
                    outputs_bob[ret++] = 1;
                }
                else outputs_bob[ret++] = 0;
            }
        }
        for(int j = t.size();j<4;j++){
            for(int c = 0;c<5;c++){
                outputs_bob[ret++] = 0;
            }
        }
        t = recipients[i];
        for(int j = 0;j<t.size();j++){
            int num = t[j] - 'a' + 1;
            for(int c = 0;c<5;c++){
                if(num & (1<<c)){
                    outputs_bob[ret++] = 1;
                }
                else outputs_bob[ret++] = 0;
            }
        }
        for(int j = t.size();j<4;j++){
            for(int c = 0;c<5;c++){
                outputs_bob[ret++] = 0;
            }
        }
    }
    // int last = 0; 
    // for(int i = 0;i<m;i++){
    //     for(int j = 0;j<M;j++){
    //         cout << outputs_bob[last++] << ' ';
    //     }   
    //     cout << endl;
    //     for(int j = 0;j<M;j++){
    //         cout << outputs_bob[last++] << ' ';
    //     }   
    //     cout << endl;
    // }
    // cout << endl;
    return ret;
}


// Circuit
int // returns l
circuit(
    /*  in */ const int la,
    /*  in */ const int lb,
    /* out */ int operations[],
    /* out */ int operands[][2],
    /* out */ int outputs_circuit[][16]
) {
    int n = la  / (K + M);
    int m = lb / 2 / M;
    int ret = la + lb;
    auto f = [&](int a,int b,int c){
        operations[ret] = a;
        operands[ret][0] = b;
        operands[ret][1] = c;
        return ret++;
    };
    for(int i = 0;i<n;i++){
        for(int j = 0;j<K;j++){
            outputs_circuit[i][j] = f(OP_ZERO,0,0);
        }
    }
    int pos0 = f(OP_ZERO,0,0);
    int pos1 = f(OP_ONE,0,0);
    for(int i = 0;i<m;i++){
        vector<int> nowval(K,pos0);
        for(int j = 0;j < n;j++){
            int now = pos1;
            for(int c = 0;c<M;c++){
                int idx1 = la + 2 * M * i + c;
                int idx2 = (K + M) * j  + c;
                now = f(OP_AND,now,f(OP_EQUAL,idx1,idx2));
            }
            for(int c = 0;c<K;c++){
                int idx = (K + M)*j + M + c;
                nowval[c] = f(OP_OR,nowval[c],f(OP_AND,now,idx));
            }
        }
        for(int j = 0;j < n;j++){
            int now = pos1;
            for(int c = 0;c<M;c++){
                int idx1 = la + 2 * M * i + M + c;
                int idx2 = (K + M) * j  + c;
                now = f(OP_AND,now,f(OP_EQUAL,idx1,idx2));
            }
            vector<int> cur(K,0);
            for(int c = 0;c<K;c++){
                cur[c] = f(OP_AND,now,nowval[c]);
            }
            int carry = pos0;
            for(int c = 0;c<K;c++){
                int tmp = outputs_circuit[j][c];
                outputs_circuit[j][c] = f(OP_XOR,outputs_circuit[j][c],f(OP_XOR,carry,cur[c]));
                carry = f(OP_OR,f(OP_AND,tmp,cur[c]),f(OP_OR,f(OP_AND,tmp,carry),f(OP_AND,carry,cur[c])));
            }
        }
    }
    return ret;
}

Compilation message

abc.cpp: In function 'int alice(int, const char (*)[5], const short unsigned int*, bool*)':
abc.cpp:37:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int j = 0;j<t.size();j++){
      |                       ~^~~~~~~~~
abc.cpp: In function 'int bob(int, const char (*)[5], const char (*)[5], bool*)':
abc.cpp:85:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int j = 0;j<t.size();j++){
      |                       ~^~~~~~~~~
abc.cpp:100:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for(int j = 0;j<t.size();j++){
      |                       ~^~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1184 KB Correct!

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1184 KB Correct!
2 Correct 3 ms 1224 KB Correct!

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1184 KB Correct!
2 Correct 3 ms 1224 KB Correct!
3 Correct 109 ms 21756 KB Correct!
4 Correct 111 ms 21792 KB Correct!

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 3500 KB Correct!
2 Correct 105 ms 73392 KB Correct!
3 Correct 129 ms 95080 KB Correct!

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 3500 KB Correct!
2 Correct 105 ms 73392 KB Correct!
3 Correct 129 ms 95080 KB Correct!
4 Correct 114 ms 73484 KB Correct!
5 Correct 152 ms 94820 KB Correct!

Subtask #6
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 3500 KB Correct!
2 Correct 105 ms 73392 KB Correct!
3 Correct 129 ms 95080 KB Correct!
4 Correct 114 ms 73484 KB Correct!
5 Correct 152 ms 94820 KB Correct!
6 Correct 106 ms 68976 KB Correct!
7 Correct 199 ms 143060 KB Correct!

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 461 ms 492868 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 461 ms 492868 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1184 KB Correct!
2 Correct 3 ms 1224 KB Correct!
3 Correct 109 ms 21756 KB Correct!
4 Correct 111 ms 21792 KB Correct!
5 Correct 7 ms 3500 KB Correct!
6 Correct 105 ms 73392 KB Correct!
7 Correct 129 ms 95080 KB Correct!
8 Correct 114 ms 73484 KB Correct!
9 Correct 152 ms 94820 KB Correct!
10 Correct 106 ms 68976 KB Correct!
11 Correct 199 ms 143060 KB Correct!
12 Runtime error 461 ms 492868 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -