| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 547591 | flashhh | Ancient Machine (JOI21_ancient_machine) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "Anna.h"
using namespace std;
int n;
vector<char> s;
void send(char x) {
if (x == 'X') {
Send(0);
Send(0);
}
else if (x == 'Y') {
Send(0);
Send(1);
}
else {
Send(1);
Send(0);
}
}
int main()
{
Anna(&n,&s);
for (int i=0;i<n;++i) send(s[i]);
return 0;
}
#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));
}
int main()
{
Bruno(n,l,s);
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);
}
return 0;
}