Submission #547594

#TimeUsernameProblemLanguageResultExecution timeMemory
547594flashhhAncient Machine (JOI21_ancient_machine)C++17
0 / 100
87 ms15068 KiB
#include <bits/stdc++.h> #include "Anna.h" using namespace std; void send(char x) { if (x == 'X') { Send(0); Send(0); } else if (x == 'Y') { Send(0); Send(1); } else { Send(1); Send(0); } } void Anna(int n,vector<char> s) { for (int i=0;i<n;++i) send(s[i]); }
#include <bits/stdc++.h> #include "Bruno.h" #define N 100005 #define pii pair<int,int> #define fi first #define se second using namespace std; struct node { int idx,val,lazy; node() {} node(int idx1,int val1,int lazy1) { idx = idx1; val = val1; lazy = lazy1; } }; int n,l; char a[N]; node it[N<<2]; pii ma,b[N],dp[N]; bool dd[N],erased[N]; vector<int> s; /*void Bruno(int &n,int &l,vector<int> &s) { cin >> n >> l; s.resize(l); for (int i=0;i<l;++i) cin >> s[i]; } void Remove(int x) { erased[x] = 1; cout << "Remove " << x-1 <<'\n'; }*/ void down(int id) { int nho = it[id].lazy; it[id<<1].val = max(it[id<<1].val, nho); it[id<<1].lazy = max(it[id<<1].lazy, nho); it[id<<1|1].val = max(it[id<<1|1].val, nho); it[id<<1|1].lazy = max(it[id<<1|1].lazy, nho); it[id].lazy = 0; } void upd_it(int id,int l,int r,int u,int v,pii val) { if (u>r || v<l) return; if (u<=l && v>=r) { if (it[id].val < val.fi) { it[id].val = val.fi; it[id].idx = val.se; } it[id].lazy = max(it[id].lazy, val.fi); return; } int mid = (l + r) >> 1; down(id); upd_it(id<<1,l,mid,u,v,val); upd_it(id<<1|1,mid+1,r,u,v,val); it[id].val = max(it[id<<1].val, it[id<<1|1].val); } pii get_it(int id,int l,int r,int u,int v) { if (u>r || v<l) return {0,0}; if (u<=l && v>=r) return {it[id].val,it[id].idx}; int mid = (l + r) >> 1; down(id); return max(get_it(id<<1,l,mid,u,v), get_it(id<<1|1,mid+1,r,u,v)); } void Bruno(int n1,int l1,vector<int> s1) { n = n1; l = l1; s = s1; for (int i=0;i<n;++i) if (s[i<<1] == 0) { if (s[i<<1|1] == 0) a[i+1] = 'X'; else a[i+1] = 'Y'; } else a[i+1] = 'Z'; int last = -1; for (int i=1;i<=n;++i) if (a[i] == 'X') last = i; else if (a[i] == 'Y') b[i].fi = last; last = -1; for (int i=n;i>=1;--i) if (a[i] == 'Z') last = i; else if (a[i] == 'Y') b[i].se = last; for (int i=1;i<=n;++i) { if (a[i] != 'Y' || b[i].fi == -1 || b[i].se == -1) continue; int l = b[i].fi; int r = b[i].se; pii kq = get_it(1,1,n,1,l); dp[i] = {kq.fi+1, kq.se}; kq = {kq.fi+1, i}; upd_it(1,1,n,r+1,n,kq); ma = max(ma, kq); } if (ma.fi == 0) { for (int i=1;i<=n;++i) Remove(i); } else { while (ma.se > 0) { dd[ma.se] = 1; ma.se = dp[ma.se].se; } for (int i=1;i<=n;++i) if (dd[i]) { int l = b[i].fi; int r = b[i].se; for (int j=l+1;j<i;++j) { erased[j] = 1; Remove(j); } for (int j=i+1;j<r;++j) { erased[j] = 1; Remove(j); } erased[i] = 1; Remove(i); } for (int i=1;i<=n;++i) if (!erased[i]) Remove(i); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...