oj.uz

Submission #489894

# Submission time Handle Problem Language Result Execution time Memory
489894 2021-11-25T02:59:04 Z i_am_noob Broken Device (JOI17_broken_device) C++17
0 / 100
 2000 ms 33764 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[]){
	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(mask,pow2(sz(vec))){
			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;
		rep1(mask,pow2(sz(vec2))){
			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:71:26: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |   rep2(i,cur,r) if(good[i]){
      |                    ~~~~~~^

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 33392 KB Time limit exceeded
2 Execution timed out 2084 ms 33276 KB Time limit exceeded
3 Execution timed out 2086 ms 33260 KB Time limit exceeded
4 Execution timed out 2077 ms 33480 KB Time limit exceeded
5 Execution timed out 2073 ms 33264 KB Time limit exceeded
6 Execution timed out 2074 ms 33468 KB Time limit exceeded
7 Execution timed out 2080 ms 33312 KB Time limit exceeded
8 Execution timed out 2077 ms 33452 KB Time limit exceeded
9 Execution timed out 2086 ms 33372 KB Time limit exceeded
10 Execution timed out 2083 ms 33348 KB Time limit exceeded
11 Execution timed out 2085 ms 33496 KB Time limit exceeded
12 Execution timed out 2095 ms 33156 KB Time limit exceeded
13 Execution timed out 2079 ms 33400 KB Time limit exceeded
14 Execution timed out 2098 ms 33168 KB Time limit exceeded
15 Execution timed out 2083 ms 33280 KB Time limit exceeded
16 Execution timed out 2088 ms 33276 KB Time limit exceeded
17 Execution timed out 2092 ms 33224 KB Time limit exceeded
18 Execution timed out 2072 ms 33612 KB Time limit exceeded
19 Execution timed out 2077 ms 33720 KB Time limit exceeded
20 Execution timed out 2097 ms 33356 KB Time limit exceeded
21 Execution timed out 2094 ms 33412 KB Time limit exceeded
22 Execution timed out 2081 ms 33572 KB Time limit exceeded
23 Execution timed out 2083 ms 33764 KB Time limit exceeded
24 Execution timed out 2075 ms 33380 KB Time limit exceeded
25 Execution timed out 2087 ms 33424 KB Time limit exceeded
26 Execution timed out 2075 ms 33320 KB Time limit exceeded
27 Execution timed out 2061 ms 33572 KB Time limit exceeded
28 Execution timed out 2087 ms 33324 KB Time limit exceeded
29 Execution timed out 2069 ms 33284 KB Time limit exceeded
30 Execution timed out 2080 ms 33596 KB Time limit exceeded
31 Execution timed out 2072 ms 33352 KB Time limit exceeded
32 Execution timed out 2089 ms 33280 KB Time limit exceeded
33 Execution timed out 2078 ms 33476 KB Time limit exceeded
34 Execution timed out 2087 ms 33244 KB Time limit exceeded
35 Execution timed out 2085 ms 33420 KB Time limit exceeded
36 Execution timed out 2070 ms 33484 KB Time limit exceeded
37 Execution timed out 2088 ms 33388 KB Time limit exceeded
38 Execution timed out 2077 ms 33416 KB Time limit exceeded
39 Execution timed out 2070 ms 33288 KB Time limit exceeded
40 Execution timed out 2072 ms 33340 KB Time limit exceeded