제출 #923932

#제출 시각아이디문제언어결과실행 시간메모리
923932daoquanglinh2007Broken Device (JOI17_broken_device)C++17
0 / 100
2070 ms1328 KiB
#include "Annalib.h" #include <bits/stdc++.h> using namespace std; #define isz(a) (int)(a).size() #define pii pair <int, int> #define fi first #define se second #define mp make_pair const int MOD1 = 1e9+7, MOD2 = 1e9+9; bool block[150], mark[150]; vector <int> arr; vector <pii> v; vector <pii>::iterator it; int binpow(int k, int MOD){ // return (2^k) % MOD; int x = 1; while (k > 0){ x = (long long)x*(1LL<<min(k, 30))%MOD; k = max(k-30, 0); } return x; } int MITM(int X, int MOD){ v.clear(); for (int i = 0; i < (1<<16); i++){ int tmp = 0; for (int j = 0; j < 16; j++){ if ((i>>j)&1) tmp = (tmp+binpow(arr[j], MOD))%MOD; } v.push_back(mp(tmp, i)); } for (int i = 0; i < (1<<15); i++){ int tmp = 0; for (int j = 0; j < 15; j++){ if ((i>>j)&1) tmp = (tmp+binpow(arr[j+16], MOD))%MOD; } tmp = (X+MOD-tmp)%MOD; if (tmp > v.back().fi) continue; int j = lower_bound(v.begin(), v.end(), mp(tmp, -1))-v.begin(); if (v[j].fi == tmp){ return (i<<15)+v[j].se; } } } void Anna(int N, long long X, int K, int P[]){ memset(block, 0, sizeof(block)); memset(mark, 0, sizeof (mark)); for (int i = 0; i < K; i++) block[P[i]] = 1; arr.clear(); for (int i = 0; i < 75; i++) if (!block[i] && isz(arr) < 31) arr.push_back(i); else mark[i] = 1; int ans1 = MITM(X%MOD1, MOD1); for (int i = 0; i < isz(arr); i++) Set(arr[i], (ans1>>i)&1); arr.clear(); for (int i = 75; i < 150; i++) if (!block[i] && isz(arr) < 31) arr.push_back(i-75); else mark[i] = 1; int ans2 = MITM(X%MOD2, MOD2); for (int i = 0; i < isz(arr); i++) Set(arr[i]+75, (ans2>>i)&1); for (int i = 0; i < 150; i++) if (mark[i]) Set(i, 0); }
#include "Brunolib.h" #include <bits/stdc++.h> using namespace std; const int MOD1 = 1e9+7, MOD2 = 1e9+9; const int R1 = 500000004, R2 = -500000003; int binpow2(int k, int MOD){ // return (2^k) % MOD; int x = 1; while (k > 0){ x = (long long)x*(1LL<<min(k, 30))%MOD; k = max(k-30, 0); } return x; } long long mul(long long x, long long y, long long MOD){ long long res = (__int128)x*(__int128)y%MOD; if (res < 0) res += MOD; return res; } long long Bruno(int N, int A[]){ long long ans1 = 0, ans2 = 0; for (int i = 0; i < 75; i++) if (A[i]) ans1 = (ans1+binpow2(i, MOD1))%MOD1; for (int i = 75; i < 150; i++) if (A[i]) ans2 = (ans2+binpow2(i-75, MOD2))%MOD2; long long MOD = (long long)MOD1*MOD2; ans1 = mul(mul(ans1, R2, MOD), MOD2, MOD); ans2 = mul(mul(ans2, R1, MOD), MOD1, MOD); return (ans1+ans2)%MOD; }

컴파일 시 표준 에러 (stderr) 메시지

Anna.cpp: In function 'int MITM(int, int)':
Anna.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
   49 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...