Submission #1164623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164623		Sang	Broken Device (JOI17_broken_device)	C++20	0 / 100	0 ms	320 KiB

Anna

#ifndef _Pbrngw_
#include "Annalib.h"
#endif // _Pbrngw_
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;


void Anna(int n, long long x, int K, int P[]){
    vector<int> bit, marked(n, 0);
    FOR (i, 0, 60) bit.pb((x>>i)&1);
    reverse(ALL(bit));
    FOR (i, 1, K){
        int x ;cin >> x;
        marked[x] = 1;
    }

    for (int i = 0; i < n; i += 3){
        if (marked[i] + marked[i+1] + marked[i+2] > 1 || bit.empty()){
            FOR (j, 0, 2) Set(i+j, 0);
            continue;
        }
        vi a;
        a.pb(bit.back()); bit.pop_back();
        if (marked[i] + marked[i+1] + marked[i+2] == 0 && !bit.empty()) a.pb(bit.back()), bit.pop_back();
        if (a.size() == 2){
            if (!a[0] && !a[1]) {
                Set(i, 1);
                Set(i+1, 1);
                Set(i+2, 0);
            }
            if (a[0] && !a[1]){
                Set(i, 0);
                Set(i+1, 1);
                Set(i+2, 1);
            }
            if (!a[0] && a[1]){
                Set(i, 1);
                Set(i+1, 0);
                Set(i+2, 1);
            }
            if (a[0] && a[1]){
                Set(i, 1);
                Set(i+1, 1);
                Set(i+2, 1);
            }
        } else {
            if (a[0]) {
                if (marked[i]) {
                    Set(i, 0);
                    Set(i+1, 1);
                    Set(i+2, 0);
                } else {
                    Set(i, 1);
                    Set(i+1, 0);
                    Set(i+2, 0);
                }
            } else {
                if (marked[i + 2]){
                    Set(i, 0);
                    Set(i+1, 1);
                    Set(i+2, 0);
                } else {
                    Set(i, 0);
                    Set(i+1, 0);
                    Set(i+2, 1);
                }
            }
        }

    }

}

#ifdef _Pbrngw_
#define MAX_K 40
#define MAX_N 150

static int Q, N, K, A[MAX_N], P[MAX_K];
static long long X;
static int min_wa = MAX_K + 1;

void Anna( int N, long long X, int K, int P[] );
long long Bruno( int N, int A[] );

void WrongAnswer( int e ){
  fprintf( stderr, "Wrong Answer [%d]\n", e );
  exit( 0 );
}

void Set( int pos, int bit ){
  if( !( 0 <= pos && pos < N ) ){
    WrongAnswer( 1 );
  }
  if( A[pos] != -1 ){
    WrongAnswer( 2 );
  }
  if( !( bit == 0 || bit == 1 ) ){
    WrongAnswer( 3 );
  }
  A[pos] = bit;
}

int main( int argc, char** argv ){
  int i, query_cnt;
  long long ans;

  scanf( "%d", &Q );

  for( query_cnt = 0; query_cnt < Q; query_cnt++ ){
    scanf( "%d %lld %d", &N, &X, &K );
    for( i = 0; i < K; i++ ){
      scanf( "%d", &P[i] );
    }

    for( i = 0; i < N; i++ ){
      A[i] = -1;
    }

    Anna( N, X, K, P );

    for( i = 0; i < N; i++ ){
      if( A[i] == -1 ){
        WrongAnswer( 4 );
      }
    }

    for( i = 0; i < K; i++ ){
      A[ P[i] ] = 0;
    }

    ans = Bruno( N, A );

    if( ans != X ){
      if( K < min_wa ){
        min_wa = K;
      }
    }
  }

  if( min_wa == 1 ){
    if( K < min_wa ){
      min_wa = K;
    }
  }

  fprintf( stderr, "Accepted\n" );
  fprintf( stderr, "L* = %d\n", min_wa - 1 );

  return 0;
}
#endif // _Pbrngw_

Bruno

#ifndef _Pbrngw_
#include "Brunolib.h"
#endif // _Pbrngw_
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;


long long Bruno(int n, int A[]){
    long long ans = 0, cur = 0;
    for (int i = 0; i < n; i += 3){
        array<int, 3> a = {A[i], A[i+1], A[i+2]};
        if ((a[0] | a[1] | a[2]) ^ 1) continue;
        if ((a[0] & a[1]) ^ a[2]){
            cur += 2;
            continue;
        }
        if (a[0] ^ (a[1] & a[2])){
            ans += (1ll<<cur);
            cur += 2;
        }
        if (a[1] ^ (a[0] & a[2])){
            ans += (1ll<<(cur+1));
            cur += 2;
        }
        if (a[1] & a[2] & a[0]){
            ans += (1ll<<cur);
            ans += (1ll<<(cur + 1));
            cur += 2;
        }
        if ((!a[0] && a[1] && !a[2]) || !(a[0] && !a[1] && !a[2])){
            ans += (1ll<<cur);
            ++cur;
        } else ++cur;
    }

    return ans;
}

#ifdef _Pbrngw_
#define MAX_K 40
#define MAX_N 150

static int Q, N, K, A[MAX_N], P[MAX_K];
static long long X;
static int min_wa = MAX_K + 1;

void Anna( int N, long long X, int K, int P[] );
long long Bruno( int N, int A[] );

void WrongAnswer( int e ){
  fprintf( stderr, "Wrong Answer [%d]\n", e );
  exit( 0 );
}

void Set( int pos, int bit ){
  if( !( 0 <= pos && pos < N ) ){
    WrongAnswer( 1 );
  }
  if( A[pos] != -1 ){
    WrongAnswer( 2 );
  }
  if( !( bit == 0 || bit == 1 ) ){
    WrongAnswer( 3 );
  }
  A[pos] = bit;
}

int main( int argc, char** argv ){
  int i, query_cnt;
  long long ans;

  scanf( "%d", &Q );

  for( query_cnt = 0; query_cnt < Q; query_cnt++ ){
    scanf( "%d %lld %d", &N, &X, &K );
    for( i = 0; i < K; i++ ){
      scanf( "%d", &P[i] );
    }

    for( i = 0; i < N; i++ ){
      A[i] = -1;
    }

    Anna( N, X, K, P );

    for( i = 0; i < N; i++ ){
      if( A[i] == -1 ){
        WrongAnswer( 4 );
      }
    }

    for( i = 0; i < K; i++ ){
      A[ P[i] ] = 0;
    }

    ans = Bruno( N, A );

    if( ans != X ){
      if( K < min_wa ){
        min_wa = K;
      }
    }
  }

  if( min_wa == 1 ){
    if( K < min_wa ){
      min_wa = K;
    }
  }

  fprintf( stderr, "Accepted\n" );
  fprintf( stderr, "L* = %d\n", min_wa - 1 );

  return 0;
}
#endif // _Pbrngw_

• Subtask 1: 0 / 100