Submission #489973

#	Time	Username	Problem	Language	Result	Execution time	Memory
489973		i_am_noob	Broken Device (JOI17_broken_device)	C++17	100 / 100	267 ms	2428 KiB

Anna

#include "Annalib.h"

#pragma GCC target("avx2")
#include<bits/stdc++.h>
//#include<x86intrin.h>
//#include<immintrin.h>
//#pragma GCC optimize("unroll-loops")
using namespace std;

#define ll long long
#define int ll
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
//#define ceiling(a,b) (((a)+(b)-1)/(b))
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 826
#endif

const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod;
const int maxn=155;

void Anna(signed n, ll x, signed k, signed p[]){
	static int de=0;
	bug(de++);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	mt19937 fix_rng(7777714);
	int arr[maxn];
	rep(n) arr[i]=i;
	shuffle(arr,arr+n,fix_rng);
	const int K=4;
	const int mod[K]={32003,32009,32027,32029};
	int re[K];
	rep(K){
		re[i]=x;
		rep2(j,i+1,K) re[i]/=mod[j];
		re[i]%=mod[i];
	}
	bool good[maxn],res[maxn];
	rep(n) good[i]=1,res[i]=0;
	rep(k) good[p[i]]=0;
	int pw2[2][maxn];
	pw2[0][0]=pw2[1][0]=1;
	rep(2) rep1(j,maxn-2) pw2[i][j+1]=pw2[i][j]*2%mod[i];
	rep1(_,K){
		int l=n/K*_,r=n/K*(_+1);
		int x,tar=0;
		rep2(i,l,r) if(good[arr[i]]==0) tar|=pow2(i-l);
		bug(n/K-__builtin_popcount(tar));
		//bug(re[_]);
		while(1){
			x=re[_]+mod[_]*uniform_int_distribution<int>(0,(1<<(n/K-60/K))-100)(rng);
			if((x&tar)==0){
				//bug(x,tar);
				rep2(i,l,r) res[arr[i]]=x>>(i-l)&1;
				break;
			}
		}
	}
 	rep(n) Set(i,res[i]);
}

Bruno

#include "Brunolib.h"

#pragma GCC target("avx2")
#include<bits/stdc++.h>
//#include<x86intrin.h>
//#include<immintrin.h>
//#pragma GCC optimize("unroll-loops")
using namespace std;

#define ll long long
#define int ll
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
//#define ceiling(a,b) (((a)+(b)-1)/(b))
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 826
#endif

const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod;
const int maxn=155;

long long Bruno(signed n, signed a[]){
	mt19937 fix_rng(7777714);
	int arr[maxn];
	rep(n) arr[i]=i;
	shuffle(arr,arr+n,fix_rng);
	const int K=4;
	const int mod[K]={32003,32009,32027,32029};
	int r[K];
	rep(K) r[i]=0;
	rep1(_,K){
		rep3(i,n/K*(_+1)-1,n/K*_) r[_]=(r[_]*2+a[arr[i]])%mod[_];
		//bug(r[_]);
	}
	int res=0;
	rep(K){
		int k=r[i];
		rep2(j,i+1,K) k*=mod[j];
		res+=k;
	}
	return res;
}

Compilation message (stderr)

Anna.cpp: In function 'void Anna(int, long long int, int, int*)':
Anna.cpp:32:18: warning: statement has no effect [-Wunused-value]
   32 | #define bug(...) 826
      |                  ^~~
Anna.cpp:41:2: note: in expansion of macro 'bug'
   41 |  bug(de++);
      |  ^~~
Anna.cpp:32:18: warning: statement has no effect [-Wunused-value]
   32 | #define bug(...) 826
      |                  ^~~
Anna.cpp:65:3: note: in expansion of macro 'bug'
   65 |   bug(n/K-__builtin_popcount(tar));
      |   ^~~
Anna.cpp:40:13: warning: unused variable 'de' [-Wunused-variable]
   40 |  static int de=0;
      |             ^~
Anna.cpp: At global scope:
Anna.cpp:40:13: warning: 'de' defined but not used [-Wunused-variable]

• Subtask 1: 100 / 100