Submission #696277

#	Time	Username	Problem	Language	Result	Execution time	Memory
696277		qwerasdfzxcl	Broken Device 2 (JOI22_device2)	C++17	100 / 100	97 ms	3744 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
    ll dp[202], S[202], M;
    vector<int> V0[202][4];
    bool first = 1;
 
vector<int> encode(ll x){ ///reverse order
    vector<int> ret;
 
    for (int z=3;z<=M;z++){
        if (x >= dp[z]) {x -= dp[z]; continue;}
 
        if (x <= 1){
            for (int i=z-3;i>=0;i--) ret.push_back(x^1);
            ret.push_back(x);
            ret.push_back(x);
            return ret;
        }
        else if (x <= 3){
            x -= 2;
            for (int i=z-3;i>=0;i--) ret.push_back(x^1^(i&1));
            ret.push_back(x);
            ret.push_back(x);
            return ret;
        }
        else if (x <= 3 + dp[z-2]){
            x -= 4;
            ret = encode(x + S[z-3]);
            ret.push_back(ret.back());
            ret.push_back(ret.back());
            return ret;
        }
        else{
            x -= 4 + dp[z-2];
            ret = encode(x + S[z-4]);
            ret.push_back(ret.back());
            ret.push_back(ret.back()^1);
            ret.push_back(ret.back());
            return ret;
        }
    }
 
    exit(1);
}
 
ll decode(vector<int> V){ ///reverse order
    int L = V.size();
    for (int i=0;i<4;i++) if (V==V0[L][i]) return S[L-1] + i;
 
    if (V[(int)V.size()-3]==V.back()) return S[L-1] + 4 + (decode(vector<int>(V.begin(), V.end()-2)) - S[L-3]);
    return S[L-1] + 4 + dp[L-2] + (decode(vector<int>(V.begin(), V.end()-3)) - S[L-4]);
}
 
void init(){
    if (!first) return;
    first = 0;
 
    dp[0] = 0, S[0] = 0;
    dp[1] = 0, S[1] = 0;
    dp[2] = 0, S[2] = 0;
    dp[3] = 2, S[3] = 2;
 
    for (int i=4;i<202;i++){
        dp[i] = dp[i-2] + dp[i-3] + 4;
        S[i] = S[i-1] + dp[i];
        if (S[i] >= (ll)1e18){
            M = i;
            break;
        }
    }
 
    for (int i=3;i<=M;i++){
        for (int j=0;j<(i==3?2:4);j++) V0[i][j] = encode(S[i-1] + j);
    }
}
 

 
 
int Declare() {
    init();
    return 139;
}
 
std::pair<std::vector<int>, std::vector<int> > Anna(long long A) {
    if (decode(encode(A))!=A){
        auto V = encode(A);
        printf("%lld -> ", A);
        for (auto &x:V) printf("%d ", x);
        printf("-> ");
 
        printf("%lld\n", decode(V));
    }
    assert(decode(encode(A)) == A);
 
    vector<int> ret[2];
    ret[0] = encode(A);
    ret[0].pop_back();
    reverse(ret[0].begin(), ret[0].end());
 
    /*printf("%lld -> ", A);
    for (auto &x:ret[0]) printf("%d ", x);
    printf("\n");*/
 
    for (int i=0;i<(int)ret[0].size();i++) ret[1].push_back((i&1)^ret[0][0]);
 
    return {ret[0], ret[1]};
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
namespace {
    ll dp[202], S[202], M;
    vector<int> V0[202][4];
    bool first = 1;
 
vector<int> encode(ll x){ ///reverse order
    vector<int> ret;
 
    for (int z=3;z<=M;z++){
        if (x >= dp[z]) {x -= dp[z]; continue;}
 
        if (x <= 1){
            for (int i=z-3;i>=0;i--) ret.push_back(x^1);
            ret.push_back(x);
            ret.push_back(x);
            return ret;
        }
        else if (x <= 3){
            x -= 2;
            for (int i=z-3;i>=0;i--) ret.push_back(x^1^(i&1));
            ret.push_back(x);
            ret.push_back(x);
            return ret;
        }
        else if (x <= 3 + dp[z-2]){
            x -= 4;
            ret = encode(x + S[z-3]);
            ret.push_back(ret.back());
            ret.push_back(ret.back());
            return ret;
        }
        else{
            x -= 4 + dp[z-2];
            ret = encode(x + S[z-4]);
            ret.push_back(ret.back());
            ret.push_back(ret.back()^1);
            ret.push_back(ret.back());
            return ret;
        }
    }
 
    exit(1);
}
 
ll decode(vector<int> V){ ///reverse order
    int L = V.size();
    for (int i=0;i<4;i++) if (V==V0[L][i]) return S[L-1] + i;
 
    if (V[(int)V.size()-3]==V.back()) return S[L-1] + 4 + (decode(vector<int>(V.begin(), V.end()-2)) - S[L-3]);
    return S[L-1] + 4 + dp[L-2] + (decode(vector<int>(V.begin(), V.end()-3)) - S[L-4]);
}
 
void init(){
    if (!first) return;
    first = 0;
 
    dp[0] = 0, S[0] = 0;
    dp[1] = 0, S[1] = 0;
    dp[2] = 0, S[2] = 0;
    dp[3] = 2, S[3] = 2;
 
    for (int i=4;i<202;i++){
        dp[i] = dp[i-2] + dp[i-3] + 4;
        S[i] = S[i-1] + dp[i];
        if (S[i] >= (ll)1e18){
            M = i;
            break;
        }
    }
 
    for (int i=3;i<=M;i++){
        for (int j=0;j<(i==3?2:4);j++) V0[i][j] = encode(S[i-1] + j);
    }
}
 
}
 
 
 
long long Bruno(std::vector<int> U) {
    init();
 
    vector<int> V = {1};
    bool flag = 0;
    if (!U[0]){
        for (auto &x:U) x ^= 1;
        flag = 1;
    }
 
    int x = 1, prv = 1, sum = 0;
    for (int i=0;i<(int)U.size();i++){
        sum += (U[i]?1:-1);
        if (prv!=-1 && sum-x==2){
            V.push_back(1);
            V.push_back(1);
            x = sum;
            prv = 1;
        }
        if (prv!=1 && sum-x==-1){
            V.push_back(0);
            V.push_back(0);
            x = sum-1;
            prv = -1;
        }
 
        if (prv==-1 && sum-x==3){
            V.push_back(1);
            V.push_back(1);
            V.push_back(1);
            x = sum;
            prv = 1;
        }
        if (prv==1 && sum-x==-2){
            V.push_back(0);
            V.push_back(0);
            V.push_back(0);
            x = sum-1;
            prv = -1;
        }
    }
 
    /*for (auto &x:V) printf("%d ", x);
    printf("\n");*/
 
    if (U.size()%4==2) sum--;
    int sum2 = 0;
    for (auto &x:V) sum2 += x?1:-1;
 
    if (V.size()>U.size()/2) V.pop_back();
    else if (V.size()<U.size()/2){
        int d = U.size()/2 - V.size();
        if (sum-sum2==d || sum-sum2==-d){
            for (int i=0;i<d;i++) V.push_back(sum-sum2>=0);
        }
        else {
            for (int i=0;i<d;i++) V.push_back(V.back()^1);
        }
    }
 
    sum2 = 0;
    for (auto &x:V) sum2 += x?1:-1;
    assert(V.size()==U.size()/2);
    assert(sum==sum2);
 
    if (flag) for (auto &x:V) x ^= 1;
 
    /*printf("Decode: ");
    for (auto &x:V) printf("%d ", x);
    printf("\n");*/
 
    reverse(V.begin(), V.end());
    V.push_back(V.back());
    return decode(V);
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 3 / 3
• Subtask 4: 12 / 12
• Subtask 5: 15 / 15
• Subtask 6: 60 / 60