QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#91915 | #5091. 大冬天题 | SenseAnone | 100 ✓ | 199ms | 155980kb | C++14 | 2.3kb | 2023-03-29 21:43:44 | 2023-03-29 21:43:45 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
int Edgecnt,head[8000005],To[8000005],nxt[8000005],W[8000005];
void AddEdge(int a,int b,int c)
{
// cerr<<a<<" "<<b<<" "<<c<<endl;
To[Edgecnt]=b; nxt[Edgecnt]=head[a]; W[Edgecnt]=c; head[a]=Edgecnt++;
To[Edgecnt]=a; nxt[Edgecnt]=head[b]; W[Edgecnt]=0; head[b]=Edgecnt++;
}
int S,T,cur[8000005],dis[8000005];
bool BFS()
{
for(int i=1;i<=T;i++) dis[i]=0;
queue<int>Q;Q.push(S);cur[S]=head[S];dis[S]=1;
while(!Q.empty())
{
int u=Q.front();Q.pop();
for(int i=head[u];~i;i=nxt[i])
{
int v=To[i];
if(!W[i]||dis[v]) continue;
dis[v]=dis[u]+1; cur[v]=head[v];
if(v==T) return true;
Q.push(v);
}
}
return false;
}
int DFS(int u,int Lim)
{
if(u==T) return Lim;
int res=0;
for(int i=cur[u];~i&&res<Lim;i=nxt[i])
{
int v=To[i]; cur[u]=i;
if(!W[i]||dis[v]!=dis[u]+1) continue;
int Tmp=DFS(v,min(Lim-res,W[i]));
if(!Tmp) dis[v]=-1;
else res+=Tmp,W[i]-=Tmp,W[i^1]+=Tmp;
}
return res;
}
int Dinic()
{
int Tmp,res=0;
while(BFS())
while((Tmp=DFS(S,1e9))) res+=Tmp;
return res;
}
int Ans[1000005];
int main() {
memset(head,-1,sizeof(head));
int n,k;
read(n);read(k);//I don't care about n
S=2*k+1; T=S+1;
for(int i=1;i<=2*k-1;i+=2)
{
AddEdge(S,(i+1)/2,1); AddEdge(k+(i+1)/2,T,1);
for(int j=0;(1<<j)<=4*k-2;j++)
{
if((1<<j)-i<=0) continue;
if((1<<j)-i>2*k-1) break;
AddEdge((i+1)/2,k+((1<<j)-i+1)/2,1);
}
}
int res=Dinic();
printf("%d\n",res);
for(int i=0;i<Edgecnt;i+=2)
{
int u=To[i^1],v=To[i],w=W[i];
if(1<=u&&u<=k&&k+1<=v&&v<=2*k&&!w) Ans[u]=(v-k);
}
for(int i=1;i<=k;i++) printf("%d\n",Ans[i]);
return 0;
}
/*
瑶草一何碧,春入武陵溪。溪上桃花无数,花上有黄鹂。我欲穿花寻路,直入白云深处,浩气展虹霓。只恐花深里,红露湿人衣。
坐玉石,欹玉枕。拂金徽。谪仙何处,无人伴我白螺杯。我为灵芝仙草,不为朱唇丹脸,长啸亦何为。醉舞下山去,明月逐人归。
*/
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 1ms
memory: 44748kb
input:
527901620 3
output:
3 1 3 2
result:
ok Accepted.
Test #2:
score: 5
Accepted
time: 2ms
memory: 45004kb
input:
423744200 1
output:
1 1
result:
ok Accepted.
Test #3:
score: 5
Accepted
time: 1ms
memory: 43436kb
input:
870873520 8
output:
8 8 7 6 5 4 3 2 1
result:
ok Accepted.
Test #4:
score: 5
Accepted
time: 1ms
memory: 44268kb
input:
796450080 10
output:
10 2 1 6 5 4 3 10 9 8 7
result:
ok Accepted.
Subtask #2:
score: 5
Accepted
Dependency #1:
100%
Accepted
Test #5:
score: 5
Accepted
time: 11ms
memory: 45828kb
input:
691352244 2
output:
2 2 1
result:
ok Accepted.
Test #6:
score: 5
Accepted
time: 1ms
memory: 45932kb
input:
537735946 4
output:
4 4 3 2 1
result:
ok Accepted.
Test #7:
score: 5
Accepted
time: 1ms
memory: 45388kb
input:
964421466 6
output:
6 2 1 6 5 4 3
result:
ok Accepted.
Test #8:
score: 5
Accepted
time: 1ms
memory: 46952kb
input:
804640404 8
output:
8 8 7 6 5 4 3 2 1
result:
ok Accepted.
Subtask #3:
score: 15
Accepted
Dependency #2:
100%
Accepted
Test #9:
score: 15
Accepted
time: 0ms
memory: 45572kb
input:
815904616 163
output:
163 1 3 2 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 35 34 33 32 31 30 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 163 162 161 160 159 158 15...
result:
ok Accepted.
Test #10:
score: 15
Accepted
time: 2ms
memory: 46800kb
input:
261467732 174
output:
174 2 1 14 13 12 11 10 9 8 7 6 5 4 3 18 17 16 15 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 174 173 172 171 170 169 168 167 166 165 164 163 162 161 160...
result:
ok Accepted.
Test #11:
score: 15
Accepted
time: 7ms
memory: 46436kb
input:
170135212 52
output:
52 4 3 2 1 12 11 10 9 8 7 6 5 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13
result:
ok Accepted.
Test #12:
score: 15
Accepted
time: 9ms
memory: 45420kb
input:
914972990 139
output:
139 1 3 2 5 4 11 10 9 8 7 6 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33...
result:
ok Accepted.
Subtask #4:
score: 10
Accepted
Dependency #3:
100%
Accepted
Test #13:
score: 10
Accepted
time: 0ms
memory: 46892kb
input:
303514006 1401
output:
1401 1 7 6 5 4 3 2 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 3...
result:
ok Accepted.
Test #14:
score: 10
Accepted
time: 1ms
memory: 46200kb
input:
651391026 1584
output:
1584 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 464 463 462 461 460 459 458 457 456 455 454 453 452 451 450 449 448 447 446 445 444 443 442 441 440 439 438 437 436 435 434 433 432 431 430 429 428 427 426 425 ...
result:
ok Accepted.
Test #15:
score: 10
Accepted
time: 4ms
memory: 46012kb
input:
196126306 1766
output:
1766 2 1 6 5 4 3 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 189 188 187 186 185 184 183 182 181 180 179 178 177 176 175 17...
result:
ok Accepted.
Test #16:
score: 10
Accepted
time: 1ms
memory: 45796kb
input:
904263684 1948
output:
1948 4 3 2 1 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 194...
result:
ok Accepted.
Subtask #5:
score: 25
Accepted
Test #17:
score: 25
Accepted
time: 137ms
memory: 122028kb
input:
1434450 717225
output:
717225 1 7 6 5 4 3 2 9 8 23 22 21 20 19 18 17 16 15 14 13 12 11 10 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 425 424 423 422 421 420 419 418 417 416 4...
result:
ok Accepted.
Test #18:
score: 25
Accepted
time: 177ms
memory: 135372kb
input:
1666706 833353
output:
833353 1 7 6 5 4 3 2 9 8 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 183 182 181 180 179 178 177 176 175 174 173 172 171 170 169 168 167 166 165 164 163...
result:
ok Accepted.
Test #19:
score: 25
Accepted
time: 165ms
memory: 141828kb
input:
1768146 884073
output:
884073 1 7 6 5 4 3 2 9 8 23 22 21 20 19 18 17 16 15 14 13 12 11 10 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30...
result:
ok Accepted.
Test #20:
score: 25
Accepted
time: 137ms
memory: 115852kb
input:
1333926 666963
output:
666963 1 3 2 13 12 11 10 9 8 7 6 5 4 19 18 17 16 15 14 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 173 172 171 170 169 168 167 166 165 164 163 162 161 1...
result:
ok Accepted.
Subtask #6:
score: 10
Accepted
Dependency #4:
100%
Accepted
Test #21:
score: 10
Accepted
time: 10ms
memory: 53828kb
input:
121768078 34399
output:
34399 1 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 33 32 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 417 416 415 414 41...
result:
ok Accepted.
Test #22:
score: 10
Accepted
time: 8ms
memory: 48788kb
input:
567903556 38581
output:
38581 1 3 2 5 4 11 10 9 8 7 6 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 181 180 179 178 177 176 175 174 173 172 171 170 169 168 167 166 165 164 163 16...
result:
ok Accepted.
Test #23:
score: 10
Accepted
time: 7ms
memory: 49084kb
input:
414440938 42763
output:
42763 1 3 2 5 4 11 10 9 8 7 6 245 244 243 242 241 240 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 189 188 187 186 185 184 183 182 181 180 179 17...
result:
ok Accepted.
Test #24:
score: 10
Accepted
time: 12ms
memory: 51116kb
input:
310652458 46946
output:
46946 2 1 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 158 157 1...
result:
ok Accepted.
Subtask #7:
score: 15
Accepted
Dependency #6:
100%
Accepted
Test #25:
score: 15
Accepted
time: 197ms
memory: 153156kb
input:
385664412 991454
output:
991454 2 1 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 34 33 32 31 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 189 188 187 186 185 184 183 182 181 180 179 178 177 176 175 174 173 ...
result:
ok Accepted.
Test #26:
score: 15
Accepted
time: 52ms
memory: 74820kb
input:
795580394 295636
output:
295636 4 3 2 1 12 11 10 9 8 7 6 5 20 19 18 17 16 15 14 13 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 212 211 210 209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 189 188 187 186 185 184 183 182 181 180 179 178 177 176 175 174 173 172 171 17...
result:
ok Accepted.
Test #27:
score: 15
Accepted
time: 135ms
memory: 108372kb
input:
639325794 599818
output:
599818 2 1 6 5 4 3 10 9 8 7 246 245 244 243 242 241 240 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 189 188 187 186 185 184 183 182 181 180 179 ...
result:
ok Accepted.
Test #28:
score: 15
Accepted
time: 163ms
memory: 147344kb
input:
514552014 904000
output:
904000 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 192 191 190 189 188 187 186 185 184 183 182 181 180 179 178 177 176 175 174 173 172 171 170 169 168 167 166 16...
result:
ok Accepted.
Subtask #8:
score: 15
Accepted
Dependency #5:
100%
Accepted
Dependency #7:
100%
Accepted
Test #29:
score: 15
Accepted
time: 20ms
memory: 60984kb
input:
4043938008620250853548463463670539178824136101118676039998249773600296234199890542107734673644890238 182956
output:
182956 4 3 2 1 12 11 10 9 8 7 6 5 20 19 18 17 16 15 14 13 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 172 171 170 169 168 167 166 165 164 163 162 161 16...
result:
ok Accepted.
Test #30:
score: 15
Accepted
time: 66ms
memory: 81552kb
input:
6809505726107869121835226914314324742765939751165985001014682212595145094113574992502730535886215434 358074
output:
358074 2 1 6 5 4 3 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 70 69 68 67 66 65 64 63 62 61 60 59 186 185 184 183 182 181 180 179 178 177 176 175 174 173 172 171 170 169 168 167 166 165 164 ...
result:
ok Accepted.
Test #31:
score: 15
Accepted
time: 199ms
memory: 155980kb
input:
2263258607536236028437491678008 1000000
output:
1000000 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 448 447 446 445 444 443 442 441 440 439 438 437 436 435 434 433 432 431 430 429 428 427 426 425 424 423 422 4...
result:
ok Accepted.
Test #32:
score: 15
Accepted
time: 196ms
memory: 152852kb
input:
36212137720579776454999866846484 1000000
output:
1000000 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 448 447 446 445 444 443 442 441 440 439 438 437 436 435 434 433 432 431 430 429 428 427 426 425 424 423 422 4...
result:
ok Accepted.