oj.uz

Submission #489972

# Submission time Handle Problem Language Result Execution time Memory
489972 2021-11-25T07:08:03 Z i_am_noob Broken Device (JOI17_broken_device) C++17
0 / 100
 2000 ms 2544 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 mod[5]={4001,4003,4007,4013,4019};
	int re[5];
	rep(5){
		re[i]=x;
		rep2(j,i+1,5) 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(_,5){
		int l=n/5*_,r=n/5*(_+1);
		int x,tar=0;
		rep2(i,l,r) if(good[arr[i]]==0) tar|=pow2(i-l);
		bug(30-__builtin_popcount(tar));
		//bug(re[_]);
		while(1){
			x=re[_]+mod[_]*uniform_int_distribution<int>(0,(1<<18)-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 mod[5]={4001,4003,4007,4013,4019};
	int r[5];
	rep(5) r[i]=0;
	rep1(_,5){
		rep3(i,n/5*(_+1)-1,n/5*_) r[_]=(r[_]*2+a[arr[i]])%mod[_];
		//bug(r[_]);
	}
	int res=0;
	rep(5){
		int k=r[i];
		rep2(j,i+1,5) 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:64:3: note: in expansion of macro 'bug'
   64 |   bug(30-__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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 2300 KB Output is correct - L* = 40
2 Correct 108 ms 2392 KB Output is correct - L* = 40
3 Correct 126 ms 2344 KB Output is correct - L* = 40
4 Correct 101 ms 2192 KB Output is correct - L* = 40
5 Correct 107 ms 2380 KB Output is correct - L* = 40
6 Correct 103 ms 2508 KB Output is correct - L* = 40
7 Correct 125 ms 2488 KB Output is correct - L* = 40
8 Correct 114 ms 2268 KB Output is correct - L* = 40
9 Correct 106 ms 2544 KB Output is correct - L* = 40
10 Correct 114 ms 2404 KB Output is correct - L* = 40
11 Correct 115 ms 2392 KB Output is correct - L* = 40
12 Correct 105 ms 2452 KB Output is correct - L* = 40
13 Execution timed out 2082 ms 332 KB Time limit exceeded
14 Correct 110 ms 2396 KB Output is correct - L* = 40
15 Correct 108 ms 2472 KB Output is correct - L* = 40
16 Correct 115 ms 2384 KB Output is correct - L* = 40
17 Correct 106 ms 2356 KB Output is correct - L* = 40
18 Correct 106 ms 2432 KB Output is correct - L* = 40
19 Execution timed out 2075 ms 904 KB Time limit exceeded
20 Execution timed out 2081 ms 588 KB Time limit exceeded
21 Correct 102 ms 2488 KB Output is correct - L* = 40
22 Correct 119 ms 2456 KB Output is correct - L* = 40
23 Correct 109 ms 2396 KB Output is correct - L* = 40
24 Correct 116 ms 2168 KB Output is correct - L* = 40
25 Correct 125 ms 2488 KB Output is correct - L* = 40
26 Correct 112 ms 2408 KB Output is correct - L* = 40
27 Correct 111 ms 2428 KB Output is correct - L* = 40
28 Correct 121 ms 2372 KB Output is correct - L* = 40
29 Correct 117 ms 2380 KB Output is correct - L* = 40
30 Correct 112 ms 2488 KB Output is correct - L* = 40
31 Correct 103 ms 2460 KB Output is correct - L* = 40
32 Correct 109 ms 2464 KB Output is correct - L* = 40
33 Correct 104 ms 2208 KB Output is correct - L* = 40
34 Correct 115 ms 2480 KB Output is correct - L* = 40
35 Correct 101 ms 2340 KB Output is correct - L* = 40
36 Correct 109 ms 2480 KB Output is correct - L* = 40
37 Correct 99 ms 2408 KB Output is correct - L* = 40
38 Correct 100 ms 2360 KB Output is correct - L* = 40
39 Correct 108 ms 2456 KB Output is correct - L* = 40
40 Correct 113 ms 2436 KB Output is correct - L* = 40