Submission #489901

#	Time	Username	Problem	Language	Result	Execution time	Memory
489901		i_am_noob	Broken Device (JOI17_broken_device)	C++17	0 / 100	2099 ms	1780 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[]){
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	const int mod[2]={Mod,Mod+2};
	int re[2];
	re[0]=x/mod[1],re[1]=x%mod[1];
	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(_,2){
		int l=0+n/2*_,r=n/2+n/2*_;
		int tot=0;
		rep2(i,l,r) tot+=good[i];
		vector<int> vec;
		int tar=min(tot/2,20ll);
		int cur;
		rep2(i,l,r) if(good[i]){
			vec.pb(i);
			tar--;
			cur=i+1;
			if(!tar) break;
		}
		vector<pii> vv;
		rep1(david,30000){
			int mask=uniform_int_distribution<int>(0,pow2(sz(vec))-1)(rng);
			int t=0;
			rep(sz(vec)) if(mask>>i&1) t=(t+pw2[_][vec[i]-l])%mod[_];
			vv.pb({t,mask});
		}
		sort(all(vv));
		vector<int> vec2;
		tar=min(tot/2,20ll);
		rep2(i,cur,r) if(good[i]){
			vec2.pb(i);
			tar--;
			if(!tar) break;
		}
		bool flag=0;
		while(1){
			int mask=uniform_int_distribution<int>(0,pow2(sz(vec2))-1)(rng);
			int t=0;
			rep(sz(vec2)) if(mask>>i&1) t=(t+pw2[_][vec2[i]-l])%mod[_];
			t=(re[_]-t+mod[_])%mod[_];
			auto it=lower_bound(all(vv),pii(t,-1));
			if(it!=vv.end()&&(*it).first==t){
				int m2=(*it).second;
				rep(sz(vec)) if(m2>>i&1) res[vec[i]]=1;
				rep(sz(vec2)) if(mask>>i&1) res[vec2[i]]=1;
				flag=1;
				break;
			}
		}
		assert(flag);
	}
 	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[]){
	const int mod[2]={Mod,Mod+2};
	int r[2];
	rep(2) r[i]=0;
	rep3(i,n/2-1,0) r[0]=(r[0]*2+a[i])%mod[0];
	rep3(i,n-1,n/2) r[1]=(r[1]*2+a[i])%mod[1];
	return r[0]*mod[1]+r[1];
}

Compilation message (stderr)

Anna.cpp: In function 'void Anna(int, long long int, int, int*)':
Anna.cpp:73:26: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |   rep2(i,cur,r) if(good[i]){
      |                    ~~~~~~^

• Subtask 1: 0 / 100