Submission #1367096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1367096		vicente1	Migrations (IOI25_migrations)	C++20	30 / 100	20 ms	456 KiB

migrations

#include <bits/stdc++.h>
#include "migrations.h"

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define all(_) _.begin(), _.end()

const int MXN = 10000;
const int INF = 1e8;
const int MOD = 1;

int dist[MXN];
int answ = 0;
int last_change = -1;

int T[MXN];

vi get_digits(int x){
    vi answ(4);
    answ[0] = (x - x%1000)/1000;
    answ[1] = (x%1000 - x%100)/100;
    answ[2] = (x%100 - x%10)/10;
    answ[3] = x%10;

    return answ;
}

int send_message(int N, int i, int Pi){

    dist[i] = dist[Pi]+1;

    if(i<N-8) {
        if(dist[i] > dist[answ]){
            answ = i;
        }
        return 0;
    }
    
    if(i == N-8){
        vi a = get_digits(answ);
        T[N-6] = a[0] - (a[0] > 4 ? 5 : 0);
        T[N-5] = a[1] - (a[1] > 4 ? 5 : 0);
        T[N-4] = a[2] - (a[2] > 4 ? 5 : 0);
        T[N-3] = a[3] - (a[3] > 4 ? 5 : 0);

        int mask = 0;
        if(a[0] > 4) mask ^= 1;
        if(a[1] > 4) mask ^= 2;

        T[N-8] = mask;

        mask = 0;
        if(a[2] > 4) mask ^= 1;
        if(a[3] > 4) mask ^= 2;
        T[N-7] = mask;

        if(dist[i] > dist[answ]) {
            answ = i;
            T[N-2] = 0;
        }

        return T[i];
    }

    if(i > N-8 && i < N-3){

        if(dist[i] > dist[answ]){
            answ = i;
            T[N-2] = 6 - (N-2-i);
        }

        return T[i];
    }

    if(i >= N-3){

        if(dist[i] > dist[answ]){
            answ = i;
            T[N-1] = 2 - (N-1-i);
        }

        if(i == N-1){
            if(answ >= N-8 && answ < N-3) T[N-1] = 3;
            if(answ < N-8) T[N-1] = 4;
        }

        return T[i];
    }

}

pii longest_path(vi S){

    int N = 10000;
    int a = S[N-6], b = S[N-5], c = S[N-4], d = S[N-3];

    if(S[N-8] == 1) a+=5;
    if(S[N-8] == 2) b+=5;
    if(S[N-8] == 3) {a+=5; b+=5;}

    if(S[N-7] == 1) c+=5;
    if(S[N-7] == 2) d+=5;
    if(S[N-7] == 3) {c+=5; d+=5;}

    int V = 1000*a + 100*b + 10*c + d;

    if(S[N-1] == 3){
        V = S[N-2] + N-2 - 6;
    }

    if(S[N-1] < 3){
        V = S[N-1] + N-1 - 2;
    }

    return {0,V};

}

Compilation message (stderr)

migrations.cpp: In function 'int send_message(int, int, int)':
migrations.cpp:95:1: warning: control reaches end of non-void function [-Wreturn-type]
   95 | }
      | ^

• Subtask 0: 0 / 0
• Subtask 1: 30 / 30
• Subtask 2: 0 / 70