oj.uz

Submission #547600

# Submission time Handle Problem Language Result Execution time Memory
547600 2022-04-11T04:31:28 Z flashhh Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 87 ms 6052 KB 
#include <bits/stdc++.h>
#include "Anna.h"

using namespace std;

void send(char x) {
    if (x == 'X') {
        Send(0);
        Send(0);
    }
    else if (x == 'Y') {
        Send(0);
        Send(1);
    }
    else {
        Send(1);
        Send(0);
    }
}

void Anna(int n,vector<char> s) {
    for (int i=0;i<n;++i) send(s[i]);
}

#include <bits/stdc++.h>
#include "Bruno.h"
#define N 100005
#define pii pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define getbit(x,y) (((x)>>(y))&1)
#define getoff(x,y) ((x)^(1<<(y)))

using namespace std;

int n,l,dp[1<<18],trace[1<<18];
char a[N];
vector<int> s;

int dq(int mask) {
    if (mask == 0) return 0;
    if (dp[mask] != -1) return dp[mask];

    vector<int> vt;
    for (int i=1;i<=n;++i)
        if (getbit(mask,i-1)) vt.pb(i);

    int ans = 0;

    for (int e=0;e<(int)vt.size();++e) {
        bool ok1 = 0; bool ok2 = 0; bool ok3 = 0;

        if (e > 0 && a[vt[e-1]] == 'X') ok1 = 1;
        if (a[vt[e]] == 'Y') ok2 = 1;
        if (e+1 < (int)vt.size() && a[vt[e+1]] == 'Z') ok3 = 1;

        int kq = dq(getoff(mask, vt[e]-1)) + (ok1&ok2&ok3);
        if (ans <= kq) {
            ans = kq;
            trace[mask] = vt[e];
        }
    }

    return dp[mask] = ans;
}

void dq2(int mask) {
    if (mask == 0) return;

    Remove(trace[mask]-1);
    dq2(getoff(mask,trace[mask]-1));
}

void Bruno(int n1,int l1,vector<int> s1) {
    n = n1; l = l1; s = s1;

    for (int i=0;i<n;++i)
        if (s[i<<1] == 0) {
            if (s[i<<1|1] == 0) a[i+1] = 'X';
            else a[i+1] = 'Y';
        }
        else a[i+1] = 'Z';

    memset(dp,-1,sizeof(dp));
    dq((1<<n)-1);
    dq2((1<<n)-1);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 2556 KB Output is correct
2 Correct 73 ms 2560 KB Output is correct
3 Correct 69 ms 2640 KB Output is correct
4 Correct 74 ms 2584 KB Output is correct
5 Correct 76 ms 2580 KB Output is correct
6 Correct 78 ms 2560 KB Output is correct
7 Correct 2 ms 1536 KB Output is correct
8 Correct 2 ms 1544 KB Output is correct
9 Correct 72 ms 2648 KB Output is correct
10 Correct 82 ms 2572 KB Output is correct
11 Correct 73 ms 2560 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 6052 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -