Submission #1203434

#TimeUsernameProblemLanguageResultExecution timeMemory
1203434TriseedotIntercastellar (JOI22_ho_t1)C++20
100 / 100
48 ms8516 KiB
// Made by ordinary newbie #pragma region setup #include <bits/stdc++.h> #include <random> #include <chrono> using namespace std; // variables #define int long long using ld = long double; using ll = long long; using ull = unsigned long long; template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>; // bitwise operations #define cnt_bit(n) __builtin_popcountll(n) #define low_bit(n) ((n) & (-(n))) #define bit(n, i) (((n) >> (i)) & 1) #define set_bit(n, i) ((n) | (1ll << (i))) #define reset_bit(n, i) ((n) & ~(1ll << (i))) #define flip_bit(n, i) ((n) ^ (1ll << (i))) // math #define sqr(n) ((n) * (n)) int log2_floor(ull n) { return n ? __builtin_clzll(1) - __builtin_clzll(n) : -1; } const ll INF = 1e18; // utils #define len(x) (int) x.size() #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() template <typename T> istream& operator>>(istream& is, vector<T>& v) { for(auto& el : v) { is >> el; } return is; } template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) { for (int i = 0; i < len(v); i++) { if (i) os << ' '; os << v[i]; } return os; } template<class... Args> auto create(size_t n, Args&&... args) { if constexpr(sizeof...(args) == 1) { return vector(n, args...); } else { return vector(n, create(args...)); } } struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } size_t operator()(pair<int, int> x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x.first + FIXED_RANDOM) ^ splitmix64(x.second + FIXED_RANDOM); } }; template<typename T, typename U> bool chmin(T& a, const U b) { if (b < a) { a = b; return true; } return false; } template<typename T, typename U> bool chmax(T& a, const U b) { if (b > a) { a = b; return true; } return false; } template<typename T> void compress(vector<T>& v) { int n = len(v); vector<pair<T, int>> u(n); for (int i = 0; i < n; i++) { u[i] = {v[i], i}; } sort(all(u)); int curr = 0; for (int i = 0; i < n; i++) { if (i != 0 && u[i].first != u[i - 1].first) curr++; v[u[i].second] = curr; } } mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); #pragma endregion void solve() { int n; cin >> n; vector<int> a(n); cin >> a; vector<int> b(n), c(n); for (int i = 0; i < n; i++) { c[i] = 1; b[i] = a[i]; while (b[i] % 2 == 0) { b[i] /= 2; c[i] *= 2; } } vector<int> p(n + 1, 0); for (int i = 0; i < n; i++) { p[i + 1] = p[i] + c[i]; } int qn; cin >> qn; while (qn--) { int x; cin >> x; int i = lower_bound(all(p), x) - p.begin(); cout << b[i - 1] << '\n'; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int tt = 1; //cin >> tt; for (int i = 1; i <= tt; i++) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...