using namespace std;
const unsigned mul = 20190812;
class Magic {
public:
Magic(unsigned state): state(state), ans(0) {}
unsigned long long retrieve() {
unsigned modulo = 0x7fffffff;
state = ((unsigned long long) state * mul + ans) % modulo;
unsigned high = state;
state = ((unsigned long long) state * mul + ans) % modulo;
return high * modulo + state;
}
int retrieve(int a, int b) {
assert (a <= b);
return (int) (retrieve() % (b - a + 1)) + a;
}
void submit(unsigned k) {
ans = ans * mul + k;
}
unsigned retrieveAns() {
return ans;
}
private:
unsigned state, ans;
};
class DataStructure {
public:
DataStructure() {
// The data structure is initially empty, until it's not.
// Implement your initialization here.
}
void add(int x, int y) {
// Add a 2D point (x, y) to the DS.
// Implement your add here.
}
void erase(int r) {
// Erase the r-th added point, of all the points that
// have still not been erased.
// Implement your erase here.
}
int size() {
// Return how many points are still in the DS
}
pair<int, int> query() {
// find two points p_i, p_j in the DS (not necessarily distinct),
// such that the dot product of these two <p_i, p_j> (i <= j)
// the smallest among all. Return (i, j).
// If the DS is empty for now, return (0, 0).
// Implement your query here.
// If there are multiple (i, j) satisfying the condition, output the lexicographically smallest pair.
}
};
int main() {
const int lim = 1E9;
int q; cin >> q;
for (int k = 0; k < q; ++k) {
unsigned state;
cin >> state;
string s;
cin >> s;
DataStructure ds;
Magic magic(state);
for (char c: s) {
if (c == 'a') {
// add one point
int x = magic.retrieve(-lim, lim);
int y = magic.retrieve(-lim, lim);
ds.add(x, y);
} else if (c == 'e') {
// select the lucky point
unsigned pos = magic.retrieve(1, ds.size());
ds.erase(pos);
} else if (c == 'q') {
// query global minimum
auto best = ds.query();
magic.submit(best.first);
magic.submit(best.second);
}
}
cout << magic.retrieveAns() << endl;
}
}
Input
The input format is a little different from traditional. Instead of giving a large file of input, the input is produced by the program above in a protocol. Thus reading the code and getting what it's doing is a fundamental step to solve this problem. The code is provided only in C++, but you should be easily converted into other languages.
As you probably have seen, the program implements a protocol to generate the input data, based on some seeds (or input of input, if you like). The program reads from standard input: in the first line an integer tt (1≤t≤201≤t≤20), which is the number of test cases; then tt cases, each in two lines: first the integer state, which is between 1010 and 107107, inclusive; then follows a non-empty string of "aeq" of length no greater than 105105. "a" means add, "e" means erase and "q" means query. You would always find something to erase, i.e., we guarantee we will not try to erase from an empty data structure.
Output
Follow the practice of the given code for the output.
Here are some hints for the sample below.
Dot product of two points pp and qq, is here, defined as the dot product from 00 to ppand 00 to qq. Specifically, if p=(a,b)p=(a,b), q=(c,d)q=(c,d), dot product of pp and qq is ac+bdac+bd.
The answer is 20190812⋅1+1=2019081320190812⋅1+1=20190813.
For sample input two, the modifications and queries are:
- Add 1st point: (−258558241,−773369213)(−258558241,−773369213). - Query: return (1,1)(1,1). - Add 2nd point: (150662440,−65439273)(150662440,−65439273). - Query: return (1,2)(1,2). - Add 3rd point: (−888171126,−337111254)(−888171126,−337111254). - Erase 3rd point added among all still alive, so 3rd was erased. - Query: return (1,2)(1,2). - Add 4th point: (−470261300,657949534)(−470261300,657949534). - Add 5th point: (−592507383,366158932)(−592507383,366158932). - Add 6th point: (635425367,329355360)(635425367,329355360). - Query: return (1,6)(1,6). - Add 7th point: (900114299,534416578)(900114299,534416578). - Erase 5th point added among all still alive, so 6th was erased. - Query: return (1,7)(1,7). - Erase 2nd point added among all still alive, so 2nd was erased. - Query: return (1,7)(1,7).
Sample input three decodes to be as follows:
- Add 1st point: (−457246811,−252726229)(−457246811,−252726229). - Add 2nd point: (−815357226,987160210)(−815357226,987160210). - Add 3rd point: (689370621,−861950583)(689370621,−861950583). - Add 4th point: (−850699215,−38670848)(−850699215,−38670848). - Add 5th point: (187488045,−980321149)(187488045,−980321149). - Add 6th point: (217752313,−264046720)(217752313,−264046720). - Query: return (2,3)(2,3). - Erase 2nd point added among all still alive, so 2nd was erased. - Query: return (3,4)(3,4). - Erase 3rd point added among all still alive, so 4th was erased. - Query: return (1,3)(1,3). - Erase 1st point added among all still alive, so 1st was erased. - Query: return (6,6)(6,6). - Erase 3rd point added among all still alive, so 6th was erased. - Query: return (3,5)(3,5). - Erase 1st point added among all still alive, so 3rd was erased. - Query: return (5,5)(5,5). - Erase 1st point added among all still alive, so 5th was erased. - Query: return (0,0)(0,0).