oj.uz

Submission #708698

# Submission time Handle Problem Language Result Execution time Memory
708698 2023-03-12T08:01:28 Z yuuhi Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 67 ms 39668 KB 
#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) ;
            }
        }
    }
//}

#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 39668 KB Output is correct
2 Correct 53 ms 39604 KB Output is correct
3 Correct 52 ms 39512 KB Output is correct
4 Correct 67 ms 39536 KB Output is correct
5 Correct 53 ms 39548 KB Output is correct
6 Correct 51 ms 39656 KB Output is correct
7 Correct 1 ms 516 KB Output is correct
8 Correct 0 ms 512 KB Output is correct
9 Correct 49 ms 39648 KB Output is correct
10 Correct 61 ms 39592 KB Output is correct
11 Correct 61 ms 39572 KB Output is correct

Subtask #2
0 / 95.0

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