QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #203997 | #89. Restore Array | Ahmed57# | 0 | 4ms | 77544kb | C++23 | 5.1kb | 2023-10-06 23:32:18 | 2024-07-04 02:17:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int lol[100001];
bool dp[5002][5002][3];
vector<array<int,2>> adj[5002];
int n;
bool solve(int i,int la,int dd){
if(i==n+1){
return 1;
}
if(dp[i][la][dd]!=-1)return dp[i][la][dd];
bool 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(e)la1 = i , la0 = i-1;
else la0 = i , la1 = i-1;
}
//cout<<la0<<" "<<la1<<" "<<i<<" "<<e<<endl;
bool ss = 1;
for(auto q:adj[i]){
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(e)la1 = i , la0 = i-1;
else la0 = i , la1 = i-1;
}
//cout<<i<<"\n";
bool ss = 1;
for(auto q:adj[i]){
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(e)la1 = i , la0 = i-1;
else la0 = i , la1 = i-1;
}
bool ss = 1;
for(auto q:adj[i]){
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(e)la1 = i , la0 = i-1;
else la0 = i , la1 = i-1;
}
bool ss = 1;
for(auto q:adj[i]){
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;
memset(lol,-1,sizeof lol);
for(int i = 0;i<m;i++){
int l,r,k,v;
cin>>l>>r>>k>>v;
l++;r++;
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});
}
}
}
if(ss==0){
cout<<-1<<endl;
return 0;
}
memset(dp,-1,sizeof dp);
if(solve(1,0,2)==0){
cout<<-1<<endl;
return 0;
}
print(1,0,2);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 77400kb
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:
0 1 0 1 1
result:
wrong output format Unexpected end of file - int32 expected
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 4ms
memory: 77544kb
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:
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 0 ...
result:
wrong output format Unexpected end of file - int32 expected
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%