| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1239052 | asdfgrace | A Light Inconvenience (CEOI23_light) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#include "light.h"
#include "sample_grader.cpp"
#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << " "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));
/*
only one call to leave:
since you can't know where that is
why does the leave work?
let's say you removed the last 17 and there are like 1024
so anyway
if you allow only 17 to be added after everything
then you can add from #32 and get the last 1...16
then how do you get the new 32
you can't
so then i guess after b is true
join won't always work
okay. so for add, i don't think it's possible to have N be 1.
that can't be it.
what would be wrong then?
umm if they're 1 2 4 8 back and i remove 4 elements i can assure that
i can add something 4 at the end!!
yeah v is empty at the start
but you'd have to add something before you can call "leave"
so i don't think "leave" can be wrong.
n can't be after join
ok so for the powers of 2
everything can be moved forward by p
then what about the rest
let's say p creates some more powers of 2?
then what could the last one be?
will there be a case in which you have to add something MORE than 5 * p
to the right of 1
well i don't think it's possible
let's say it's currently
ok say you MORE THAN DOUBLE n
that will always be good
because at least one element has to be <= n/2 more than 1
*/
bool b;
long long n;
vector<long long> v;
void prepare() {
b = false;
n = 1;
v.push_back(1);
}
pair<long long, vector<long long>> join(long long p) {
n += p;
if (!b) {
vector<long long> v2(1, n);
for (long long x = 1; x < n - 1; x *= 2) {
v2.push_back(n - x);
}
v2.push_back(1);
reverse(v2.begin(), v2.end());
for (int i = 0; i < (int) v2.size(); i++) {
int lb = lower_bound(v.begin(), v.end(), v2[i] - p) - v.begin();
assert(lb != v.size() && v[lb] <= v2[i]);
}
v = v2;
return make_pair(p, v2);
} else {
v.push_back(n);
return make_pair(p, v);
}
}
pair<long long, vector<long long>> leave(long long p) {
b = true;
n -= p;
while (v.size() && v.back() >= n) v.pop_back();
v.push_back(n);
return make_pair(p, v);
}