oj.uz

Submission #489901

# Submission time Handle Problem Language Result Execution time Memory
489901 2021-11-25T03:06:09 Z i_am_noob Broken Device (JOI17_broken_device) C++17
0 / 100
 2000 ms 1780 KB 
#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]);
}

#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 1432 KB Time limit exceeded
2 Execution timed out 2088 ms 1436 KB Time limit exceeded
3 Execution timed out 2091 ms 1432 KB Time limit exceeded
4 Execution timed out 2084 ms 1532 KB Time limit exceeded
5 Execution timed out 2085 ms 1528 KB Time limit exceeded
6 Execution timed out 2076 ms 1568 KB Time limit exceeded
7 Execution timed out 2088 ms 1568 KB Time limit exceeded
8 Execution timed out 2084 ms 1660 KB Time limit exceeded
9 Execution timed out 2084 ms 1548 KB Time limit exceeded
10 Execution timed out 2088 ms 1404 KB Time limit exceeded
11 Execution timed out 2079 ms 1740 KB Time limit exceeded
12 Execution timed out 2061 ms 1628 KB Time limit exceeded
13 Execution timed out 2093 ms 1420 KB Time limit exceeded
14 Execution timed out 2083 ms 1532 KB Time limit exceeded
15 Execution timed out 2091 ms 1484 KB Time limit exceeded
16 Execution timed out 2088 ms 1548 KB Time limit exceeded
17 Execution timed out 2089 ms 1780 KB Time limit exceeded
18 Execution timed out 2085 ms 1572 KB Time limit exceeded
19 Execution timed out 2071 ms 1484 KB Time limit exceeded
20 Execution timed out 2087 ms 1500 KB Time limit exceeded
21 Execution timed out 2091 ms 1500 KB Time limit exceeded
22 Execution timed out 2082 ms 1576 KB Time limit exceeded
23 Execution timed out 2077 ms 1680 KB Time limit exceeded
24 Execution timed out 2099 ms 1392 KB Time limit exceeded
25 Execution timed out 2073 ms 1612 KB Time limit exceeded
26 Execution timed out 2093 ms 1420 KB Time limit exceeded
27 Execution timed out 2079 ms 1560 KB Time limit exceeded
28 Execution timed out 2081 ms 1480 KB Time limit exceeded
29 Execution timed out 2070 ms 1656 KB Time limit exceeded
30 Execution timed out 2085 ms 1516 KB Time limit exceeded
31 Execution timed out 2082 ms 1472 KB Time limit exceeded
32 Execution timed out 2095 ms 1500 KB Time limit exceeded
33 Execution timed out 2097 ms 1484 KB Time limit exceeded
34 Execution timed out 2081 ms 1592 KB Time limit exceeded
35 Execution timed out 2094 ms 1488 KB Time limit exceeded
36 Execution timed out 2097 ms 1356 KB Time limit exceeded
37 Execution timed out 2099 ms 1380 KB Time limit exceeded
38 Execution timed out 2090 ms 1380 KB Time limit exceeded
39 Execution timed out 2093 ms 1424 KB Time limit exceeded
40 Execution timed out 2073 ms 1576 KB Time limit exceeded