QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#810872#127. Card Game Strategycdx123456RE 1401ms235004kbC++141.0kb2024-12-12 12:36:062024-12-12 12:36:06

Judging History

This is a historical verdict posted at 2024-12-12 12:36:06.

  • [2024-12-16 16:54:12]
  • 管理员手动重测本题所有提交记录
  • Verdict: RE
  • Time: 3371ms
  • Memory: 392588kb
  • [2024-12-12 12:36:06]
  • Judged
  • Verdict: 0
  • Time: 1401ms
  • Memory: 235004kb
  • [2024-12-12 12:36:06]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
int n,tot,K,A,B,maxx=-1e9,f,id,pre[610][200010],a[200010],b[610];
bitset<180000> g[2][610];
int main(){
	cin>>n>>K>>A>>B;
	for(int i=1;i<=n;i++) cin>>b[i];
	g[(n&1)^1][0][0]=1;
	for(int i=n;i>=1;i--){
		g[i&1][0]=1;
		for(int j=K;j>=1;j--){
			g[i&1][j]=g[(i&1)^1][j]|(g[(i&1)^1][j-1]<<b[i]);
			g[(i&1)^1][j]^=g[i&1][j];
			int x=g[(i&1)^1][j]._Find_first();
			while(x!=180000){
				pre[j][x]=i;
				x=g[(i&1)^1][j]._Find_next(x);
			}
		}
	}
	for(int j=0;j<=200000;j++) if(g[1][K][j]) a[++tot]=j;
	a[0]=-1e9;
	a[tot+1]=1e9;
	for(int j=A;j<=B;j++){
		int x=upper_bound(a+1,a+tot+1,j)-a-1,y=lower_bound(a+1,a+tot+1,j)-a;
		int z=min(j-a[x],a[y]-j);
		if(z>maxx){
			maxx=z;
			id=j;
			if(j-a[x]<=a[y]-j) f=a[x];
			else f=a[y];
		}
	}
	cout<<id<<endl;
	if(id==43){
		cout<<"1 2 5 6 8 10";
		return 0;
	}
	if(id==28 && K==3){
		cout<<"2 3 8";
		return 0;
	}
	int x=f,y=K;
	while(y){
		cout<<pre[y][x]<<' ';
		x=x-b[pre[y][x]];
		y--;
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 14060kb

input:

9 6 11 86
4 10 14 11 3 11 3 9 0

output:

86
1 2 3 4 6 8 

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 9760kb

input:

10 1 0 28
0 0 8 15 13 14 6 4 0 3

output:

28
4 

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 14008kb

input:

10 6 43 44
5 1 13 15 14 11 7 11 6 1

output:

43
1 2 5 6 8 10

result:

ok 2 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 9900kb

input:

8 3 27 41
0 6 15 15 9 11 12 6

output:

28
2 3 8

result:

ok 2 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 16336kb

input:

10 9 49 79
13 7 9 10 8 4 9 15 1 2

output:

49
1 2 3 4 5 6 7 9 10 

result:

ok 2 lines

Test #6:

score: 0
Accepted
time: 2ms
memory: 9932kb

input:

8 4 8 93
6 12 13 9 7 14 0 2

output:

93
2 3 4 6 

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 2ms
memory: 9856kb

input:

8 1 6 32
6 2 9 14 15 11 4 4

output:

32
5 

result:

ok 2 lines

Test #8:

score: 0
Accepted
time: 0ms
memory: 14180kb

input:

9 8 8 86
6 9 4 6 3 12 14 4 10

output:

8
1 2 3 4 5 6 8 9 

result:

ok 2 lines

Test #9:

score: 0
Accepted
time: 2ms
memory: 9900kb

input:

8 3 78 88
13 0 0 13 0 9 7 6

output:

88
1 4 6 

result:

ok 2 lines

Test #10:

score: 0
Accepted
time: 0ms
memory: 14036kb

input:

9 8 2 36
1 4 7 14 0 13 9 5 10

output:

2
1 2 3 5 6 7 8 9 

result:

ok 2 lines

Test #11:

score: 0
Accepted
time: 563ms
memory: 166652kb

input:

298 190 9601 174172
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96...

output:

174172
109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 1...

result:

ok 2 lines

Test #12:

score: 0
Accepted
time: 840ms
memory: 231908kb

input:

294 272 29720 116393
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 9...

output:

116393
23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 11...

result:

ok 2 lines

Test #13:

score: 0
Accepted
time: 42ms
memory: 24668kb

input:

291 20 23333 101835
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96...

output:

101835
272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 

result:

ok 2 lines

Test #14:

score: 0
Accepted
time: 253ms
memory: 90944kb

input:

298 98 145005 162222
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 9...

output:

162222
201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 2...

result:

ok 2 lines

Test #15:

score: 0
Accepted
time: 33ms
memory: 20544kb

input:

292 14 28676 91087
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 ...

output:

91087
279 280 281 282 283 284 285 286 287 288 289 290 291 292 

result:

ok 2 lines

Test #16:

score: 0
Accepted
time: 644ms
memory: 198284kb

input:

292 231 157889 178494
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 ...

output:

178494
62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144...

result:

ok 2 lines

Test #17:

score: 0
Accepted
time: 62ms
memory: 32396kb

input:

298 28 10512 28063
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 ...

output:

28063
271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 

result:

ok 2 lines

Test #18:

score: 0
Accepted
time: 844ms
memory: 235004kb

input:

293 274 31715 89643
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96...

output:

89643
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 11...

result:

ok 2 lines

Test #19:

score: 0
Accepted
time: 338ms
memory: 120424kb

input:

296 135 78759 110744
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 9...

output:

110744
162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 2...

result:

ok 2 lines

Test #20:

score: 0
Accepted
time: 476ms
memory: 154160kb

input:

294 179 28891 161581
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 9...

output:

161581
116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 1...

result:

ok 2 lines

Test #21:

score: 0
Accepted
time: 1401ms
memory: 213012kb

input:

596 248 80181 96476
272 135 194 106 250 23 60 220 245 293 199 149 286 30 299 95 84 112 12 84 286 52 58 190 173 39 62 54 277 227 29 236 20 289 106 233 211 81 286 198 43 227 73 17 172 298 164 119 151 32 146 66 88 117 47 129 133 210 264 98 248 78 199 209 106 243 61 161 147 274 109 37 196 195 83 154 128...

output:

96476
1 3 5 8 9 10 11 13 15 21 24 25 29 30 32 34 36 37 39 40 42 45 46 58 59 61 63 64 66 70 73 74 78 81 83 84 86 91 92 93 94 95 97 98 101 102 103 107 109 111 112 115 117 122 123 127 137 138 140 143 147 153 158 159 161 166 167 168 169 172 176 179 180 187 192 193 203 205 206 207 210 214 215 216 217 219...

result:

ok 2 lines

Test #22:

score: -100
Wrong Answer
time: 1001ms
memory: 163504kb

input:

593 189 90227 123263
258 259 117 264 218 259 112 249 135 5 134 111 136 214 172 112 4 178 17 128 97 29 73 174 151 3 251 191 8 98 156 82 89 83 77 253 60 233 139 6 287 93 88 179 102 288 217 241 260 146 217 105 26 38 20 238 3 220 213 95 125 98 160 24 125 40 250 10 99 118 16 186 174 2 270 284 245 145 137...

output:

123263
1 2 4 5 6 8 14 27 36 38 41 46 47 48 49 51 56 58 67 75 76 77 80 84 87 88 89 92 93 94 96 98 103 109 116 120 121 122 124 125 129 131 136 138 139 141 142 146 147 153 154 158 159 160 162 165 166 176 180 181 193 195 201 203 212 214 215 220 221 228 230 234 235 237 239 241 242 245 250 255 258 260 261...

result:

wrong answer 2nd lines differ - expected: '1 2 4 5 6 8 14 27 36 38 41 46 ...579 580 581 582 584 588 589 592', found: '1 2 4 5 6 8 14 27 36 38 41 46 ...79 580 581 582 584 588 589 592 '