QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #203982 | #89. Restore Array | Ahmed57# | 0 | 8ms | 200060kb | C++23 | 4.9kb | 2023-10-06 23:10:54 | 2024-07-04 02:17:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int lol[100001];
int dp[5002][5002][2];
vector<array<int,2>> adj[5002];
int n;
int solve(int i,int la,int dd){
if(i==n+1){
return 1;
}
if(dp[i][la][dd]!=-1)return dp[i][la][dd];
int c1 = 0;
if(lol[i]==-1){
for(int e = 0;e<2;e++){
int la0 = 0, la1 =0;
if(e==dd){
if(dd==0)la0 = i , la1 = la;
else la1 = i , la0 = la;
}else{
if(dd==0)la1 = i , la0 = i-1;
else la0 = i , la1 = i-1;
}
bool ss = 1;
for(auto q:adj[e]){
if(q[1]==0){
if(la0<q[0]){
ss = 0;
}
}else{
if(la1<q[0]){
ss = 0;
}
}
}
if(ss){
if(la0==i){
c1 = max(c1,solve(i+1,la1,0));
}else{
c1 = max(c1,solve(i+1,la0,1));
}
}
}
}else{
for(int e = lol[i];e<=lol[i];e++){
int la0 =0, la1 = 0;
if(e==dd){
if(dd==0)la0 = i , la1 = la;
else la1 = i , la0 = la;
}else{
if(dd==0)la1 = i , la0 = i-1;
else la0 = i , la1 = i-1;
}
bool ss = 1;
for(auto q:adj[e]){
if(q[1]==0){
if(la0<q[0]){
ss = 0;
}
}else{
if(la1<q[0]){
ss = 0;
}
}
}
if(ss){
if(la0==i){
c1 = max(c1,solve(i+1,la1,0));
}else{
c1 = max(c1,solve(i+1,la0,1));
}
}
}
}
return dp[i][la][dd] = c1;
}void print(int i,int la,int dd){
if(i==n+1){
return ;
}
if(lol[i]==-1){
for(int e = 0;e<2;e++){
int la0 = 0, la1 =0;
if(e==dd){
if(dd==0)la0 = i , la1 = la;
else la1 = i , la0 = la;
}else{
if(dd==0)la1 = i , la0 = i-1;
else la0 = i , la1 = i-1;
}
bool ss = 1;
for(auto q:adj[e]){
if(q[1]==0){
if(la0<q[0]){
ss = 0;
}
}else{
if(la1<q[0]){
ss = 0;
}
}
}
if(ss){
if(la0==i&&solve(i+1,la1,0)){
cout<<e<<" ";
print(i+1,la1,0);
break;
}else{
cout<<e<<" ";
print(i+1,la0,1);
break;
}
}
}
}else{
for(int e = lol[i];e<=lol[i];e++){
int la0 =0, la1 = 0;
if(e==dd){
if(dd==0)la0 = i , la1 = la;
else la1 = i , la0 = la;
}else{
if(dd==0)la1 = i , la0 = i-1;
else la0 = i , la1 = i-1;
}
bool ss = 1;
for(auto q:adj[e]){
if(q[1]==0){
if(la0<q[0]){
ss = 0;
}
}else{
if(la1<q[0]){
ss = 0;
}
}
}
if(ss){
if(la0==i&&solve(i+1,la1,0)){
cout<<e<<" ";
print(i+1,la1,0);
break;
}else{
cout<<e<<" ";
print(i+1,la0,1);
break;
}
}
}
}
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int m;
cin>>n>>m;
bool ss = 1;
for(int i = 0;i<m;i++){
int l,r,k,v;
cin>>l>>r>>k>>v;
if(k==1&&v==1){
for(int j = l;j<=r;j++){
if(lol[j]==0){
ss = 0;
}
lol[j] = 1;
}
}if(k==(r-l+1)&&v==0){
for(int j = l;j<=r;j++){
if(lol[j]==1){
ss = 0;
}
lol[j] = 0;
}
}else{
if(k==1){
adj[r].push_back({l,0});
}else{
adj[r].push_back({l,1});
}
}
}
memset(dp,-1,sizeof dp);
cout<<solve(1,0,0)<<endl;
if(solve(1,0,0)==0){
cout<<-1<<endl;
return 0;
}
print(1,0,0);
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 8ms
memory: 199092kb
input:
8 13 0 1 2 1 3 5 1 1 5 7 2 1 0 2 2 0 2 5 3 1 3 7 4 1 2 2 1 0 0 1 1 0 2 7 5 1 2 4 1 0 0 4 2 0 4 5 2 1 1 2 1 0
output:
1 0 0 1 1 1 0 0 0
result:
wrong answer your plan does not meet the constraint #3
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 7ms
memory: 200060kb
input:
4992 9040 331 4442 1 0 3489 4173 1 0 393 4420 1 0 1324 2666 1 0 1317 4131 1 0 399 3010 1 0 1843 4154 1 0 1119 4876 1 0 4216 4980 1 0 2003 4370 1 0 769 1927 1 0 934 3414 1 0 2072 2507 1 0 215 3526 1 0 1493 4107 1 0 539 1643 1 0 2783 4338 1 0 967 1190 1 0 1374 2868 1 0 34 1378 1 0 71 1418 1 0 2120 223...
output:
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong output format Extra information in the output file
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%