Submission #708698

#	Time	Username	Problem	Language	Result	Execution time	Memory
708698		yuuhi	Ancient Machine (JOI21_ancient_machine)	C++17	5 / 100	67 ms	39668 KiB

Anna

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

#define f first
#define s second
#define double long double
#define _size(x) ((int)((x).size()))

using namespace std ;

typedef pair< int , int > ii ;

//namespace {
    void Anna (int n , vector< char > s) {
        for (int i = 0 ; i < n ; ++ i) {
            if (s[i] == 'X') {
                Send(0) ;
                Send(0) ;
            }
            else if (s[i] == 'Y') {
                Send(0) ;
                Send(1) ;
            }
            else {
                Send(1) ;
                Send(0) ;
            }
        }
    }
//}

Bruno

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

#define f first
#define s second
#define double long double
#define _size(x) ((int)((x).size()))

using namespace std ;

typedef pair< int , int > ii ;

//namespace {
    void Bruno (int n , int L , vector< int > b) {
        vector< int > a(n) ;
        for (int i = 0 ; i < n ; ++ i) {
            a[i] = (b[i << 1] << 1) | b[i << 1 | 1] ;
        }
        vector< int > f(1 << n , 0) ;
        vector< vector< int > > l(n , vector< int > (1 << n , -1)) , r(n , vector< int > (1 << n , -1)) ;
        for (int mask = 1 ; mask < (1 << n) ; ++ mask) {
            for (int i = 0 , last = -1 ; i < n ; ++ i) if (mask >> i & 1) {
                l[i][mask] = last ;
                last = i ;
            }
            for (int i = n - 1 , last = -1 ; i >= 0 ; -- i) if (mask >> i & 1) {
                r[i][mask] = last ;
                last = i ;
            }

            for (int i = 0 ; i < n ; ++ i) if (mask >> i & 1) {
                int cost = (a[i] == 1 && l[i][mask] != -1 && r[i][mask] != -1 && a[l[i][mask]] == 0 && a[r[i][mask]] == 2) ;
                f[mask] = max(f[mask] , f[mask ^ (1 << i)] + cost) ;
            }
        }

        for (int mask = (1 << n) - 1 ; mask > 0 ;) {
            for (int i = 0 ; i < n ; ++ i) if (mask >> i & 1) {
                int cost = (a[i] == 1 && l[i][mask] != -1 && r[i][mask] != -1 && a[l[i][mask]] == 0 && a[r[i][mask]] == 2) ;
                if (f[mask] == f[mask ^ (1 << i)] + cost) {
                    mask ^= (1 << i) ;
                    Remove(i) ;
                    break ;
                }
            }
        }
    }
//}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 95