#include #include using namespace std; using namespace atcoder; using mint = modint998244353; #define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl #define print(var) std::cout<<#var<<"="<<(var)< #define vvi vector #define vvvi vector #define ll long long #define vll vector #define vvll vector #define vvvll vector #define vmi vector #define vvmi vector #define vvvmi vector #define vs vector #define pii pair #define vpii vector #define vvpii vector #define bit(x,i)(((x)>>(i))&1) #define inf (1<<30) #define INF (1ll<<60) template inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } template T nibutan(T ok, T ng, const F &f){while(abs(ok-ng)>1){T mid = (ok+ng)/2;(f(mid)?ok:ng) = mid;}return ok;} template vector digit(T x){vector res; while(x>0){res.push_back(x%10); x/=10;} return res;} #ifdef LOCAL #include "../../cpp-dump/dump.hpp" #else #define cpp_dump #endif static uint32_t xor128(void){ static uint32_t x=123456789,y=362436069,z=521288629,w=88675123; uint32_t t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); } int randrange(int a){return (uint64_t(xor128()) * a >> 32); } double randDouble(double a,double b){return a+(b-a)*xor128()/(double)ULONG_MAX;} inline double get_time() { using namespace std::chrono; return duration_cast(system_clock::now().time_since_epoch()).count(); } double start_time = get_time(); struct IO{ int n; vll a,b; IO(){} void input(){ cin >> n; a.resize(n); b.resize(n); for(int i=0;i> a[i] >> b[i]; } } }; struct State{ int n; unordered_set used; vi seq; State(IO& io) : n(io.n){ used.insert(0); } void add(int i, int j, const IO& io){ if(i > seq.size()){ cerr << "error : " << i << " is out of range" << endl; return; } if(used.find(j) != used.end()){ cerr << "error : " << j << " is already used" << endl; return; } if(i == seq.size()) seq.push_back(j); else seq.insert(seq.begin()+i, j); used.insert(j); } void swap(int i, int j, const IO& io){ if(i>=seq.size()){ cerr << "seq size is " << seq.size() << " but i is " << i << endl; return; } if(used.find(j) != used.end()){ cerr << "error : " << j << " is already used" << endl; return; } used.erase(seq[i]); seq[i] = j; used.insert(j); } void del(int i, const IO& io){ if(i>=seq.size()){ cerr << "seq size is " << seq.size() << " but i is " << i << endl; return; } used.erase(seq[i]); seq.erase(seq.begin()+i); } void update(const IO& io){ int coin = randrange(10); if(seq.size()==0 || (coin < 3 && seq.size() < n-1)){ int i = randrange(seq.size()+1); int j; do{ j = randrange(n-1)+1; }while(used.find(j) != used.end()); add(i,j,io); } else if(coin < 6 && seq.size() > 0){ int i = randrange(seq.size()); del(i,io); } else{ int i,j; i = randrange(seq.size()); do{ j = randrange(n-1)+1; }while(used.find(j) != used.end()); swap(i,j,io); } } double get_score(const IO& io){ ll a = io.a[0]; ll b = io.b[0]; for(int i=0;i