QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #204018 | #89. Restore Array | Ahmed57# | 20 | 449ms | 131612kb | C++23 | 6.2kb | 2023-10-06 23:54:49 | 2024-07-04 02:17:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int lol[100001];
bool dp[5002][5002][3];
bool vis[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(vis[i][la][dd])return dp[i][la][dd];
bool c1 = 0;
vis[i][la][dd] = 1;
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<<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));
}
}
}
}
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;
if(n<=18){
vector<array<int,4>> ops;
for(int i = 0;i<m;i++){
int l,r,k,v;
cin>>l>>r>>k>>v;
ops.push_back({l,r,k,v});
}
for(int mask = 0;mask<(1<<n);mask++){
bool ss = 1;
for(auto e:ops){
int cnt = 0 , cnt2 = 0;
for(int w = e[0];w<=e[1];w++){
if(mask&(1<<w))cnt++;
else cnt2++;
}
if(e[3]==0){
if(cnt2<e[2]){
ss = 0;
break;
}
}else{
if(cnt2>=e[2]){
ss = 0;break;
}
}
}
if(ss){
for(int i = 0;i<n;i++){
if(mask&(1<<i))cout<<1<<" ";
else cout<<0<<" ";
}
return 0;
}
}
cout<<-1<<endl;
return 0;
}
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;
}
}else 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});
//cout<<l<<" "<<r<<" "<<0<<"pp"<<endl;
}else{
adj[r].push_back({l,1});
//cout<<l<<" "<<r<<" "<<1<<"pp"<<endl;
}
}
}
if(ss==0){
cout<<-1<<endl;
return 0;
}
if(solve(1,0,2)==0){
cout<<-1<<endl;
return 0;
}
print(1,0,2);
}
详细
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 1ms
memory: 3616kb
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 1 0
result:
ok your plan is correct!
Test #2:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
7 10 0 3 4 1 2 3 1 0 1 2 2 0 1 3 2 0 0 5 3 0 0 5 5 1 1 4 2 0 2 4 1 0 1 3 3 0 3 5 2 0
output:
1 0 0 0 1 0 0
result:
ok your plan is correct!
Test #3:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
18 190 12 15 3 0 12 12 1 0 11 11 1 0 5 17 3 0 3 4 1 0 1 14 7 0 15 16 1 0 2 13 10 0 4 11 1 0 0 12 2 0 2 10 6 0 6 6 1 0 12 12 1 0 5 8 1 0 2 7 3 0 13 15 2 0 5 14 6 0 14 14 1 0 9 11 1 0 5 17 13 1 6 17 5 0 0 6 1 0 0 9 3 0 10 14 3 0 5 12 1 0 0 17 16 0 0 15 7 0 1 14 8 0 14 16 3 1 1 3 3 1 4 16 11 0 0 16 4 0...
output:
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0
result:
ok your plan is correct!
Test #4:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
17 195 12 16 3 1 5 7 3 1 2 10 5 1 5 7 2 1 4 10 7 1 3 9 4 1 8 13 5 1 4 9 2 1 2 7 5 1 1 5 2 1 5 12 3 1 10 13 3 1 5 7 3 1 1 3 3 1 0 9 2 1 3 16 7 1 3 6 3 1 14 16 2 1 3 8 3 1 1 1 1 1 2 15 14 1 1 6 4 1 4 8 1 0 1 2 2 1 4 12 9 1 4 4 1 0 7 13 2 0 2 11 2 0 5 16 2 0 0 3 4 1 9 10 2 1 13 14 2 1 3 8 3 1 11 14 3 1...
output:
1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0
result:
ok your plan is correct!
Test #5:
score: 0
Accepted
time: 7ms
memory: 3832kb
input:
18 200 0 17 13 1 0 14 4 0 3 9 1 1 1 6 5 1 8 9 2 1 9 14 3 1 5 15 1 0 10 16 7 1 7 12 3 0 10 17 1 0 1 16 16 1 11 16 5 0 2 15 12 1 4 13 5 0 3 16 10 0 10 16 7 1 4 10 6 1 6 9 1 0 1 12 7 1 4 16 8 0 0 1 1 0 0 12 8 1 1 4 4 1 1 13 8 0 5 14 6 0 7 16 8 1 7 14 4 0 3 15 11 1 0 6 3 1 12 15 3 0 12 15 2 0 4 17 11 1 ...
output:
-1
result:
ok No Solution!
Test #6:
score: 0
Accepted
time: 4ms
memory: 3788kb
input:
17 195 0 9 10 1 2 11 1 0 4 6 1 0 4 11 1 0 16 16 1 1 4 5 2 1 0 3 1 1 2 12 5 1 2 13 4 0 8 15 3 1 2 3 2 1 6 12 6 0 5 11 3 1 10 16 4 0 12 13 1 1 3 15 6 1 9 14 6 1 2 10 3 0 1 13 3 1 4 7 1 0 0 4 2 1 0 10 9 1 5 14 5 1 1 6 5 1 5 6 2 1 9 14 5 0 1 6 2 1 0 14 7 0 5 6 1 0 12 14 2 0 2 7 4 0 0 4 4 0 12 14 1 0 1 7...
output:
-1
result:
ok No Solution!
Test #7:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
16 181 6 7 2 1 4 12 2 0 6 12 6 1 8 8 1 0 4 14 3 0 1 12 5 0 15 15 1 1 9 13 4 0 6 7 2 1 2 12 5 0 5 11 7 1 2 4 2 1 4 5 2 1 10 11 2 0 14 14 1 1 9 14 1 0 3 5 2 1 7 11 4 0 6 13 8 1 5 8 4 1 3 11 7 1 3 13 5 0 9 10 2 0 6 11 4 0 3 8 3 0 13 14 2 1 9 11 2 0 5 8 1 0 4 9 4 0 2 2 1 0 1 13 1 0 2 11 5 0 5 14 4 0 0 3...
output:
0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 1
result:
ok your plan is correct!
Test #8:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
16 172 10 15 1 0 11 12 1 0 3 9 5 1 7 11 5 1 8 10 1 0 5 10 4 0 1 15 11 1 9 11 3 0 4 13 7 0 1 3 2 0 5 10 4 0 7 15 8 1 3 11 4 0 9 15 4 0 7 15 6 0 7 10 3 0 7 13 6 0 8 13 6 1 3 9 4 0 5 9 5 1 7 8 1 0 1 14 4 0 10 14 4 0 11 15 2 0 2 13 6 0 6 11 1 0 1 10 10 1 10 12 1 0 2 10 8 1 5 8 3 0 3 11 4 0 10 10 1 0 3 1...
output:
1 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1
result:
ok your plan is correct!
Test #9:
score: 0
Accepted
time: 3ms
memory: 3540kb
input:
18 198 13 14 1 0 1 5 3 0 7 12 3 1 15 15 1 1 4 15 10 1 8 11 2 1 3 12 3 0 10 15 5 1 0 3 1 0 9 16 1 0 7 7 1 1 10 11 2 1 15 17 1 1 11 16 2 0 10 13 4 1 6 10 5 1 2 11 8 1 2 6 4 1 12 12 1 0 0 9 8 1 11 15 2 0 3 14 12 1 11 14 4 1 1 4 3 0 5 14 9 1 2 9 2 0 2 6 1 0 1 17 13 1 6 15 6 1 3 7 4 1 3 4 2 1 6 9 3 1 7 1...
output:
1 0 0 0 1 1 1 1 0 1 1 1 0 0 1 1 1 1
result:
ok your plan is correct!
Test #10:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
17 6 1 1 1 0 2 3 1 0 0 0 1 1 2 13 8 1 6 8 1 0 2 5 2 0
output:
1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 0 0
result:
ok your plan is correct!
Subtask #2:
score: 13
Accepted
Test #11:
score: 13
Accepted
time: 184ms
memory: 115292kb
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:
ok your plan is correct!
Test #12:
score: 0
Accepted
time: 76ms
memory: 106644kb
input:
4952 9496 4222 4300 1 0 2892 4392 1 0 4158 4700 1 0 2720 3468 1 0 3002 3114 1 0 1010 4681 1 0 629 4392 1 0 734 2030 1 0 1024 2836 1 0 299 2880 1 0 3728 4858 1 0 1616 2861 1 0 2716 2938 1 0 1265 2892 1 0 1695 1778 1 0 1414 2231 1 0 47 4835 1 0 1554 3489 1 0 2591 3178 1 0 2424 4665 1 0 1089 2460 1 0 2...
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 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 ...
result:
ok your plan is correct!
Test #13:
score: 0
Accepted
time: 449ms
memory: 131612kb
input:
4995 9192 257 4428 1 0 2504 2636 1 0 208 4875 1 0 1462 2898 1 0 1000 2298 1 0 4596 4745 1 0 614 4072 1 0 1425 1941 1 0 2378 4165 1 0 496 1556 1 0 255 4838 1 0 76 2176 1 0 349 3143 1 0 1325 4409 1 0 854 3653 1 0 4656 4945 1 0 2957 4396 1 0 784 4891 1 0 4488 4917 1 0 1721 4188 1 0 231 4748 1 0 282 332...
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:
ok your plan is correct!
Test #14:
score: 0
Accepted
time: 27ms
memory: 99020kb
input:
4938 9603 2957 4666 1 0 2348 3586 1 0 3501 3789 1 0 2741 4713 1 0 1217 1254 1 0 192 2857 1 0 1242 2716 1 0 2315 4140 1 0 2464 2912 1 0 189 2590 1 0 4150 4701 1 0 3604 3942 1 0 2491 2801 1 0 1009 2819 1 0 1508 3589 1 0 88 4021 1 0 86 487 1 0 2857 4336 1 0 1738 4473 1 0 1385 1969 1 0 3187 4675 1 0 753...
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 1 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 ...
result:
ok your plan is correct!
Test #15:
score: 0
Accepted
time: 6ms
memory: 6132kb
input:
4923 9528 377 1664 1 0 629 4786 1 0 0 3255 1 0 785 3022 1 1 1009 2063 1 1 3041 4632 1 1 156 3479 1 0 107 4762 1 0 140 1296 1 1 1542 4475 1 0 935 2058 1 0 1230 2832 1 0 2616 2756 1 1 1184 1951 1 0 481 4708 1 0 550 3300 1 0 791 1219 1 0 2423 4289 1 1 1558 2502 1 0 720 2744 1 0 3282 4611 1 1 1795 2077 ...
output:
-1
result:
ok No Solution!
Test #16:
score: 0
Accepted
time: 5ms
memory: 6116kb
input:
4993 9026 407 4008 1 0 1175 3810 1 0 1935 3175 1 0 702 3112 1 0 759 4120 1 0 350 2774 1 1 3711 3813 1 1 1723 2232 1 0 1938 2653 1 1 3780 4873 1 0 1765 4967 1 1 1444 3182 1 1 2189 3485 1 0 1101 1385 1 0 1684 1892 1 1 658 1163 1 0 4143 4382 1 0 2683 4035 1 1 539 4555 1 0 2188 4158 1 0 1081 4527 1 1 42...
output:
-1
result:
ok No Solution!
Subtask #3:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #17:
score: 25
Accepted
time: 20ms
memory: 97628kb
input:
4938 9881 1814 3083 1 0 2918 2958 41 1 2085 2909 825 1 2595 3342 748 1 1147 2469 1323 1 2697 2734 1 0 407 4791 1 0 568 2847 1 0 2500 2905 1 0 1670 3662 1 0 1692 3400 1709 1 35 436 402 1 1393 2755 1 0 1074 4777 3704 1 552 1519 1 0 3216 3566 351 1 1841 2502 1 0 3 1708 1706 1 90 3062 1 0 1593 2428 1 0 ...
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 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 ...
result:
ok your plan is correct!
Test #18:
score: 0
Accepted
time: 25ms
memory: 99068kb
input:
4948 9938 597 2134 1 0 192 2940 2749 1 116 4688 4573 1 449 2324 1 0 3526 4697 1172 1 4178 4738 1 0 4472 4845 1 0 323 1072 1 0 724 4075 3352 1 2828 3622 1 0 712 980 269 1 891 1227 1 0 4117 4895 779 1 419 1627 1 0 927 2579 1653 1 1961 3667 1707 1 1065 3028 1 0 2275 4477 2203 1 3396 3451 56 1 1273 1660...
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 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 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 ...
result:
ok your plan is correct!
Test #19:
score: -25
Wrong Answer
time: 8ms
memory: 97668kb
input:
4957 9852 86 2229 2144 1 838 3854 1 0 177 2427 1 0 1516 2489 974 1 3404 3854 1 0 2667 3472 1 0 260 834 1 0 3096 4769 1674 1 1288 3517 2230 1 60 4378 4319 1 1905 2286 1 0 21 1956 1 0 2956 3222 1 0 122 4000 1 0 4089 4678 590 1 425 4031 3607 1 1424 2198 1 0 1107 1949 843 1 4262 4638 1 0 327 4871 1 0 12...
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 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer your plan does not meet the constraint #2340
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%