oj.uz

Submission #72767

# Submission time Handle Problem Language Result Execution time Memory
72767 2018-08-26T23:29:26 Z Benq Broken Device (JOI17_broken_device) C++14
100 / 100
 66 ms 4096 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

// #define LOCAL 

/*#ifndef LOCAL
#include "Brunolib.h"
#endif

long long Bruno( int N, int A[] ){
	ll cur = 0;
	for (int i = N-3; i >= 0; i -= 3) {
		int x = 4*A[i]+2*A[i+1]+A[i+2];
		switch(x) {
			case 0:
				break;
			case 1:
				cur *= 4;
				break;
			case 2: 
				cur *= 2;
				break;
			case 3:
				cur = 2*cur+1;
				break;
			case 4:
				cur = 2*cur+1;
				break;
			case 5: 
				cur = 4*cur+2;
				break;
			case 6:
				cur = 4*cur+1;
				break;
			case 7:
				cur = 4*cur+3;
				break;
		}
	}
	return cur;
}*/

#ifndef LOCAL 
    #include "Annalib.h"
#else
    void Set( int pos, int bit );
#endif 

void Anna( int N, long long X, int K, int P[] ){
	int bad[150];
	F0R(i,N) bad[i] = 0;
	F0R(i,K) bad[P[i]] = 1;
	int ind = 0;
	while (ind < N) {
		int sum = bad[ind]+bad[ind+1]+bad[ind+2];
		if (sum > 1) {
			Set(ind,0); Set(ind+1,0); Set(ind+2,0);
		} else if (sum == 1) {
			if (bad[ind]) {
				Set(ind,0); Set(ind+1,1); Set(ind+2,X%2); X /= 2;
			} else if (bad[ind+1]) {
				if (X % 2) {
					Set(ind,1); Set(ind+1,0); Set(ind+2,0); X /= 2;
				} else {
					Set(ind+1,0); Set(ind+2,1); Set(ind,(X%4)/2); X /= 4;
				}
			} else {
				if (X % 2) {
					Set(ind,1); Set(ind+1,0); Set(ind+2,0);
				} else {
					Set(ind,0); Set(ind+1,1); Set(ind+2,0);
				}
				X /= 2;
			}
		} else {
			if (X % 4 == 0) {
				Set(ind,0); Set(ind+1,0); Set(ind+2,1);
			} else if (X % 4 == 1) {
				Set(ind,1); Set(ind+1,1); Set(ind+2,0);
			} else if (X % 4 == 2) {
				Set(ind,1); Set(ind+1,0); Set(ind+2,1);
			} else {
				Set(ind,1); Set(ind+1,1); Set(ind+2,1);
			}
			X /= 4;
		}
		ind += 3;
	}
}

#ifdef LOCAL 

#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 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( stdout, "Accepted\n" );
  fprintf( stdout, "L* = %d\n", min_wa - 1 );
  
  return 0;
}
#endif

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
* if you have no idea just guess the appropriate well-known algo instead of doing nothing :/
*/
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

// #define LOCAL 

#ifndef LOCAL
#include "Brunolib.h"
#endif

long long Bruno( int N, int A[] ){
	ll cur = 0;
	for (int i = N-3; i >= 0; i -= 3) {
		int x = 4*A[i]+2*A[i+1]+A[i+2];
		switch(x) {
			case 0:
				break;
			case 1:
				cur *= 4;
				break;
			case 2: 
				cur *= 2;
				break;
			case 3:
				cur = 2*cur+1;
				break;
			case 4:
				cur = 2*cur+1;
				break;
			case 5: 
				cur = 4*cur+2;
				break;
			case 6:
				cur = 4*cur+1;
				break;
			case 7:
				cur = 4*cur+3;
				break;
		}
	}
	return cur;
}

/*#ifndef LOCAL 
    #include "Annalib.h"
#else
    void Set( int pos, int bit );
#endif 

void Anna( int N, long long X, int K, int P[] ){
	int bad[150];
	F0R(i,N) bad[i] = 0;
	F0R(i,K) bad[P[i]] = 1;
	int ind = 0;
	while (ind < N) {
		int sum = bad[ind]+bad[ind+1]+bad[ind+2];
		if (sum > 1) {
			Set(ind,0); Set(ind+1,0); Set(ind+2,0);
		} else if (sum == 1) {
			if (bad[ind]) {
				Set(ind,0); Set(ind+1,1); Set(ind+2,X%2); X /= 2;
			} else if (bad[ind+1]) {
				if (X % 2) {
					Set(ind,1); Set(ind+1,0); Set(ind+2,0); X /= 2;
				} else {
					Set(ind+1,0); Set(ind+2,1); Set(ind,(X%4)/2); X /= 4;
				}
			} else {
				if (X % 2) {
					Set(ind,1); Set(ind+1,0); Set(ind+2,0);
				} else {
					Set(ind,0); Set(ind+1,1); Set(ind+2,0);
				}
				X /= 2;
			}
		} else {
			if (X % 4 == 0) {
				Set(ind,0); Set(ind+1,0); Set(ind+2,1);
			} else if (X % 4 == 1) {
				Set(ind,1); Set(ind+1,1); Set(ind+2,0);
			} else if (X % 4 == 2) {
				Set(ind,1); Set(ind+1,0); Set(ind+2,1);
			} else {
				Set(ind,1); Set(ind+1,1); Set(ind+2,1);
			}
			X /= 4;
		}
		ind += 3;
	}
}*/

#ifdef LOCAL 

#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 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( stdout, "Accepted\n" );
  fprintf( stdout, "L* = %d\n", min_wa - 1 );
  
  return 0;
}
#endif

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
* if you have no idea just guess the appropriate well-known algo instead of doing nothing :/
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2800 KB Output is correct - L* = 40
2 Correct 48 ms 3368 KB Output is correct - L* = 40
3 Correct 44 ms 3552 KB Output is correct - L* = 40
4 Correct 45 ms 3552 KB Output is correct - L* = 40
5 Correct 45 ms 3552 KB Output is correct - L* = 40
6 Correct 44 ms 3576 KB Output is correct - L* = 40
7 Correct 47 ms 3576 KB Output is correct - L* = 40
8 Correct 51 ms 3584 KB Output is correct - L* = 40
9 Correct 45 ms 3592 KB Output is correct - L* = 40
10 Correct 57 ms 3840 KB Output is correct - L* = 40
11 Correct 44 ms 3840 KB Output is correct - L* = 40
12 Correct 41 ms 3840 KB Output is correct - L* = 40
13 Correct 43 ms 3840 KB Output is correct - L* = 40
14 Correct 66 ms 3840 KB Output is correct - L* = 40
15 Correct 45 ms 3840 KB Output is correct - L* = 40
16 Correct 48 ms 3840 KB Output is correct - L* = 40
17 Correct 46 ms 3840 KB Output is correct - L* = 40
18 Correct 51 ms 3840 KB Output is correct - L* = 40
19 Correct 45 ms 3840 KB Output is correct - L* = 40
20 Correct 48 ms 3840 KB Output is correct - L* = 40
21 Correct 44 ms 3840 KB Output is correct - L* = 40
22 Correct 48 ms 4096 KB Output is correct - L* = 40
23 Correct 44 ms 4096 KB Output is correct - L* = 40
24 Correct 47 ms 4096 KB Output is correct - L* = 40
25 Correct 41 ms 4096 KB Output is correct - L* = 40
26 Correct 47 ms 4096 KB Output is correct - L* = 40
27 Correct 43 ms 4096 KB Output is correct - L* = 40
28 Correct 44 ms 4096 KB Output is correct - L* = 40
29 Correct 48 ms 4096 KB Output is correct - L* = 40
30 Correct 43 ms 4096 KB Output is correct - L* = 40
31 Correct 48 ms 4096 KB Output is correct - L* = 40
32 Correct 40 ms 4096 KB Output is correct - L* = 40
33 Correct 39 ms 4096 KB Output is correct - L* = 40
34 Correct 41 ms 4096 KB Output is correct - L* = 40
35 Correct 39 ms 4096 KB Output is correct - L* = 40
36 Correct 39 ms 4096 KB Output is correct - L* = 40
37 Correct 40 ms 4096 KB Output is correct - L* = 40
38 Correct 40 ms 4096 KB Output is correct - L* = 40
39 Correct 40 ms 4096 KB Output is correct - L* = 40
40 Correct 40 ms 4096 KB Output is correct - L* = 40