Submission #971037

#TimeUsernameProblemLanguageResultExecution timeMemory
971037ALeonidouDigital Circuit (IOI22_circuit)C++17
4 / 100
554 ms2756 KiB
#include "circuit.h" #include <vector> #include <iostream> using namespace std; #define ll long long #define F first #define S second #define pb push_back #define sz(x) (ll)x.size() #define endl "\n" typedef vector <int> vi; typedef pair <ll, ll> ii; typedef vector <ii> vii; #define MOD 1000002022 #define dbg(x) cout<<#x<<": "<<x<<endl; #define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl; #define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl; void printVct(vi &v){ for (ll i =0; i<sz(v); i++){ cout<<v[i]<<" "; } cout<<endl; } ll mpow(ll a, ll b){ if (b == 0) return 1; if (b % 2) return (a * (mpow((a*a)%MOD, b/2)% MOD)) % MOD; return mpow((a*a)%MOD, b/2)%MOD; } ll n,m; vi p,a; ll dif; ll ans; void init(int N, int M, vector <int> P, vector<int> A) { n= N, m = M; p = P; a = A; //subtask 4,5: ll treeHeight = 0; ll p = m; while (p){ p/=2; treeHeight++; } // dbg(treeHeight); dif = 1; ll p2 = 1; // dbg(m-1-treeHeight); for (ll i = 0; i<=m-1-treeHeight; i++){ dif = (dif + p2) % MOD; p2 = (p2 * 2) % MOD; } // dbg(dif); //calc ans: ll curOff = 0; for (ll i = 0; i<m; i++){ if (!a[i]) curOff++; } ll all = mpow(2, n); ans = (all - ((dif * curOff) % MOD) + MOD) % MOD; // dbg(ans); } int count_ways(int L, int R) { //subtask 4: L = R ll l = L-n; if (a[l] == 1){ a[l] = 0; ans = (ans - dif + MOD) % MOD; } else{ a[l] = 1; ans = (ans + dif) % MOD; } return ans; } /* 3 4 4 -1 0 0 1 1 2 2 1 1 1 1 4 4 4 4 5 5 4 4 7 8 1 -1 0 0 1 1 2 2 3 3 4 4 5 5 6 6 1 1 1 1 1 1 1 1 10 10 */ /* subtask 1: ll l = L-n, r = R-n; ll curOn = 0; for (ll i =0; i<m; i++){ if (i >= l && i <= r){ a[i] = !a[i]; } if (a[i]) curOn++; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...