oj.uz

Submission #417320

# Submission time Handle Problem Language Result Execution time Memory
417320 2021-06-03T14:49:26 Z lyc Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 58 ms 2980 KB 
#include "Anna.h"
#include <vector>

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<int,int> ii;

namespace {

    int N, res[1<<18], pa[1<<18];
    vector<char> S;

    int dp(int x) {
        if (x == 0) return 0;
        if (~res[x]) return res[x];

        res[x] = -1;
        for (int y = x; y;) {
            int b = y&-y, j = __builtin_ctz(b);

            int add = 0;
            if (S[j] == 'Y') {
                int p = x & ((1<<j)-1), q = x ^ p ^ b;
                if (p != 0 && q != 0) {
                    int r = 31-__builtin_clz(p), s = __builtin_ctz(q);
                    if (S[r] == 'X' && S[s] == 'Z') ++add;
                }
            }

            int cur = dp(x ^ b) + add;
            if (cur > res[x]) {
                pa[x] = j;
                res[x] = cur;
            }
            y ^= b;
        }

        return res[x];
    }

}

void Anna(int _N, std::vector<char> _S) {
    N = _N;
    S = _S;

    memset(res,-1,sizeof res);
    memset(pa,-1,sizeof pa);
    dp((1<<N)-1);

    vector<int> seq;
    int u = (1<<N)-1;
    while (pa[u] != -1) {
        seq.push_back(pa[u]);
        u = u ^ (1<<pa[u]);
    }

    //cout << "SEQ ";
    for (int& x : seq) {
        //cout << x << '\n';
        RFOR(i,4,0){
            Send((x&(1<<i)) > 0);
        }
    }
}

#include "Bruno.h"
#include <vector>

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<int,int> ii;

namespace {

}  // namespace

void Bruno(int N, int L, std::vector<int> A) {
    int p = 0;
    FOR(i,0,N-1){
        int x = 0;
        FOR(j,0,4){
            x *= 2;
            x += A[p++];
        }
        Remove(x);
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2476 KB Output is correct
2 Correct 44 ms 2576 KB Output is correct
3 Correct 37 ms 2608 KB Output is correct
4 Correct 31 ms 2460 KB Output is correct
5 Correct 31 ms 2512 KB Output is correct
6 Correct 30 ms 2600 KB Output is correct
7 Correct 1 ms 2536 KB Output is correct
8 Correct 2 ms 2532 KB Output is correct
9 Correct 31 ms 2512 KB Output is correct
10 Correct 58 ms 2580 KB Output is correct
11 Correct 36 ms 2512 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 2980 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -