QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #330415 | #6537. One, Two, Three | zuishuai | WA | 1ms | 4016kb | C++14 | 6.2kb | 2024-02-17 15:39:49 | 2024-02-17 15:39:49 |
Judging History
answer
#include<bits/stdc++.h>
// #define int long long
#define uint unsigned long long
#define il inline
#define ct const
#define dl double
#define pk push_back
#define fi first
#define se second
#define pii pair<int,int>
// #define inf (int)(1000000000000000000)
using namespace std;
bool ppp;
il int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();
}
return x*f;
}
char f__[40];
il void write(int x){
int cnt=0;
if(x<0){
putchar('-');x=-x;
}
if(!x) putchar('0');
while(x){
f__[cnt++]=x%10+'0';x/=10;
}
while(cnt) putchar(f__[--cnt]);
}
il void Mx(int &a,int b){
a=a>b?a:b;
}
#define N 110
int n,a[N],ans;
struct node{
int b,c,d,e;
il bool operator<(ct node &x)ct{
return b==x.b?(c==x.c?(d==x.d?e<x.e:d<x.d):c<x.c):b<x.b;
}
il bool operator==(ct node &x)ct{
return b==x.b&&c==x.c&&d==x.d&&e==x.e;
}
};
struct piii{
int a,b,c;
};
vector<int> g[N];
vector<node> V[N];
vector<node> S[N];
vector<int> res1,res2;
vector<int> V1,V3;
vector<pii> V12,V32;
vector<piii> VV;
il int find(int i,int b,int c,int d,int e){
return lower_bound(V[i].begin(),V[i].end(),(node){b,c,d,e})-V[i].begin();
}
bool pppp;
signed main(){
n=read();
for(int i=1;i<=n;++i) a[i]=read();
S[0].pk((node){0,0,0,0});
for(int i=1;i<=n;++i){
for(auto x:S[i-1]){
int b=x.b,c=x.c,d=x.d,e=x.e;
S[i].pk((node){b,c,d,e});
if(a[i]==1){
S[i].pk((node){x.b+1,x.c,x.d,x.e});
if(e) S[i].pk((node){x.b,x.c,x.d,x.e-1});
}
if(a[i]==2){
if(b) S[i].pk((node){x.b-1,x.c+1,x.d,x.e});
if(d) S[i].pk((node){x.b,x.c,x.d-1,x.e+1});
}
if(a[i]==3){
S[i].pk((node){x.b,x.c,x.d+1,x.e});
if(c) S[i].pk((node){x.b,x.c-1,x.d,x.e});
}
}
sort(S[i].begin(),S[i].end());
S[i].resize(unique(S[i].begin(),S[i].end())-S[i].begin());
}
int tot=0;
for(int i=0;i<=n;++i) tot+=(int)S[i].size();
// cerr<<tot<<" ";
for(int i=0;i<=n;++i) for(auto x:S[i]) V[i].pk(x);
for(int i=0;i<=n;++i){
int sz=V[i].size();
while(sz--) g[i].pk(0);
}
for(int i=1;i<=n;++i){
for(int j=0;j<(int)V[i-1].size();++j){
int b=V[i-1][j].b,c=V[i-1][j].c,d=V[i-1][j].d,e=V[i-1][j].e,to;
to=find(i,b,c,d,e);
Mx(g[i][to],g[i-1][j]);
if(a[i]==1){
to=find(i,b+1,c,d,e);
Mx(g[i][to],g[i-1][j]);
if(e){
to=find(i,b,c,d,e-1);
Mx(g[i][to],g[i-1][j]+1);
}
}
if(a[i]==2){
if(b){
to=find(i,b-1,c+1,d,e);
Mx(g[i][to],g[i-1][j]);
}
if(d){
to=find(i,b,c,d-1,e+1);
Mx(g[i][to],g[i-1][j]);
}
}
if(a[i]==3){
to=find(i,b,c,d+1,e);
Mx(g[i][to],g[i-1][j]);
if(c){
to=find(i,b,c-1,d,e);
Mx(g[i][to],g[i-1][j]+1);
}
}
}
}
int p=0,q=-1;
for(int i=0;i<(int)V[n].size();++i){
if(q<g[n][i]){
p=i;q=g[n][i];
}
}
write(q);putchar('\n');
for(int i=n;i;--i){
// cerr<<i<<" "<<V[i][p].b<<" "<<V[i][p].c<<" "<<V[i][p].d<<" "<<V[i][p].e<<" "<<g[i][p]<<"\n";
for(int j=0;j<(int)V[i-1].size();++j){
int b=V[i-1][j].b,c=V[i-1][j].c,d=V[i-1][j].d,e=V[i-1][j].e,to;
to=find(i,b,c,d,e);
if(to==p&&g[i][to]==g[i-1][j]){
// cerr<<i<<" "<<g[i][to]<<" "<<g[i-1][j]<<"\n";
p=j;break;
}
if(a[i]==1){
to=find(i,b+1,c,d,e);
if(to==p&&g[i][to]==g[i-1][j]){
p=j;res1.pk(i);break;
}
if(e){
to=find(i,b,c,d,e-1);
if(to==p&&g[i][to]==g[i-1][j]+1){
p=j;res2.pk(i);break;
}
}
}
if(a[i]==2){
if(b){
to=find(i,b-1,c+1,d,e);
if(to==p&&g[i][to]==g[i-1][j]){
p=j;res1.pk(i);break;
}
}
if(d){
to=find(i,b,c,d-1,e+1);
if(to==p&&g[i][to]==g[i-1][j]){
p=j;res2.pk(i);break;
}
}
}
if(a[i]==3){
to=find(i,b,c,d+1,e);
if(to==p&&g[i][to]==g[i-1][j]){
p=j;res2.pk(i);break;
}
if(c){
to=find(i,b,c-1,d,e);
if(to==p&&g[i][to]==g[i-1][j]+1){
p=j;res1.pk(i);break;
}
}
}
}
}
reverse(res1.begin(),res1.end());
for(auto j:res2){
if(a[j]==1){
V1.pk(j);
}
if(a[j]==2){
if(!V1.empty()){
V12.pk(pii(V1.back(),j));V1.pop_back();
}
}
if(a[j]==3){
if(!V12.empty()){
VV.pk((piii){V12.back().fi,V12.back().se,j});V12.pop_back();
}
}
}
for(int i=0;i<(int)VV.size();++i) swap(VV[i].a,VV[i].c);
for(auto j:res1){
if(a[j]==1){
V1.pk(j);
}
if(a[j]==2){
if(!V1.empty()){
V12.pk(pii(V1.back(),j));V1.pop_back();
}
}
if(a[j]==3){
if(!V12.empty()){
VV.pk((piii){V12.back().fi,V12.back().se,j});V12.pop_back();
}
}
}
for(auto x:VV){
write(x.a-1);putchar(' ');write(x.b-1);putchar(' ');write(x.c-1);putchar('\n');
}
cerr<<"\n"<<(dl)clock()/CLOCKS_PER_SEC;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4012kb
input:
6 3 1 2 2 3 1
output:
2 0 3 5 1 2 4
result:
ok count=2
Test #2:
score: 0
Accepted
time: 0ms
memory: 4016kb
input:
6 2 1 3 1 3 2
output:
0
result:
ok count=0
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3956kb
input:
3000 1 1 1 1 1 3 1 1 3 3 1 3 1 1 2 3 1 1 2 1 2 1 3 3 3 1 1 2 1 2 2 3 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 3 3 1 1 2 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 2 3 1 1 1 1 3 3 2 1 3 1 1 2 3 1 2 3 1 1 1 2 1 1 1 1 2 3 2 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 3 1 3 3 1 1 1 1 3 1 1 2 1 1 1 3 3 1 1 1 1 2 1 1 1 1 1 2 3 3 1...
output:
0
result:
wrong answer the number of matches is different