oj.uz

Submission #489973

# Submission time Handle Problem Language Result Execution time Memory
489973 2021-11-25T07:13:41 Z i_am_noob Broken Device (JOI17_broken_device) C++17
100 / 100
 267 ms 2428 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[]){
	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]);
}

#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

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

# Verdict Execution time Memory Grader output
1 Correct 238 ms 2332 KB Output is correct - L* = 40
2 Correct 197 ms 2208 KB Output is correct - L* = 40
3 Correct 236 ms 2224 KB Output is correct - L* = 40
4 Correct 232 ms 2308 KB Output is correct - L* = 40
5 Correct 225 ms 2300 KB Output is correct - L* = 40
6 Correct 192 ms 2224 KB Output is correct - L* = 40
7 Correct 251 ms 2160 KB Output is correct - L* = 40
8 Correct 225 ms 2296 KB Output is correct - L* = 40
9 Correct 198 ms 2180 KB Output is correct - L* = 40
10 Correct 223 ms 2232 KB Output is correct - L* = 40
11 Correct 206 ms 2384 KB Output is correct - L* = 40
12 Correct 221 ms 2244 KB Output is correct - L* = 40
13 Correct 211 ms 2368 KB Output is correct - L* = 40
14 Correct 210 ms 2264 KB Output is correct - L* = 40
15 Correct 216 ms 2348 KB Output is correct - L* = 40
16 Correct 216 ms 2260 KB Output is correct - L* = 40
17 Correct 198 ms 2272 KB Output is correct - L* = 40
18 Correct 200 ms 2200 KB Output is correct - L* = 40
19 Correct 211 ms 2364 KB Output is correct - L* = 40
20 Correct 218 ms 2164 KB Output is correct - L* = 40
21 Correct 207 ms 2208 KB Output is correct - L* = 40
22 Correct 267 ms 2192 KB Output is correct - L* = 40
23 Correct 205 ms 2160 KB Output is correct - L* = 40
24 Correct 245 ms 2276 KB Output is correct - L* = 40
25 Correct 222 ms 2172 KB Output is correct - L* = 40
26 Correct 235 ms 2228 KB Output is correct - L* = 40
27 Correct 205 ms 2428 KB Output is correct - L* = 40
28 Correct 219 ms 2164 KB Output is correct - L* = 40
29 Correct 194 ms 2204 KB Output is correct - L* = 40
30 Correct 218 ms 2248 KB Output is correct - L* = 40
31 Correct 234 ms 2216 KB Output is correct - L* = 40
32 Correct 203 ms 2292 KB Output is correct - L* = 40
33 Correct 215 ms 2140 KB Output is correct - L* = 40
34 Correct 217 ms 2272 KB Output is correct - L* = 40
35 Correct 210 ms 2332 KB Output is correct - L* = 40
36 Correct 252 ms 2256 KB Output is correct - L* = 40
37 Correct 200 ms 2184 KB Output is correct - L* = 40
38 Correct 208 ms 2344 KB Output is correct - L* = 40
39 Correct 212 ms 2276 KB Output is correct - L* = 40
40 Correct 215 ms 2392 KB Output is correct - L* = 40