QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #15799 | #679. Time Zones | huco | 100 ✓ | 1ms | 2008kb | C++20 | 697b | 2021-11-11 16:52:07 | 2022-05-03 22:17:02 |
Judging History
answer
#include<cstdio>
#include<cstdlib>
typedef unsigned long long ull;
const int N=70;
int n,i,a[N],b[N],lim[N],off[N],f[N];char s[9];
inline int min(int a,int b){return a<b?a:b;}
void dfs(int x,ull S){
if(x==-1){
for(i=0;i<n;i++)printf("%d ",f[i]);
std::exit(0);
}
int u=min(lim[x],f[x+1]-off[x+1]);
if(u<0)return;
ull U=S&((1ULL<<(u+1))-1);
for(int i=n-1;~i;i--)if(U>>i&1)f[x]=i,dfs(x-1,S^(1ULL<<i));
}
int main(){
scanf("%d",&n);
for(f[n]=100;i<n;i++){
char s[9];
scanf("%s",s);
a[i]=(s[0]-'0')*10+s[1]-'0';
b[i]=(s[2]-'0')*10+s[3]-'0';
lim[i]=n-1-a[i];
if(i)off[i]=a[i-1]-a[i]+(b[i-1]>=b[i]);
}
dfs(n-1,(1ULL<<n)-1);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 9.09091
Accepted
time: 1ms
memory: 1828kb
input:
24 0000 0001 0002 0003 0004 0005 0006 0007 0008 0009 0010 0011 0012 0013 0014 0015 0016 0017 0018 0019 0020 0021 0022 0023
output:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
result:
ok single line: '0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 '
Test #2:
score: 9.09091
Accepted
time: 1ms
memory: 1964kb
input:
24 0000 0001 0002 0003 0004 0005 0006 0007 0008 0009 0010 0011 0012 0013 0014 0015 0016 0017 0018 0019 0020 0021 0022 0023
output:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
result:
ok single line: '0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 '
Test #3:
score: 9.09091
Accepted
time: 1ms
memory: 1828kb
input:
24 0000 0101 1602 1103 1404 1905 2006 1707 0008 0909 1810 0011 0212 1413 0314 0815 0416 0517 1018 1119 1320 1721 2322 0623
output:
11 16 3 8 7 2 1 4 22 14 5 23 21 9 20 15 19 18 13 12 10 6 0 17
result:
ok single line: '11 16 3 8 7 2 1 4 22 14 5 23 21 9 20 15 19 18 13 12 10 6 0 17 '
Test #4:
score: 9.09091
Accepted
time: 1ms
memory: 1772kb
input:
32 0006 0900 0639 0634 0616 1259 2056 2000 2807 0425 2246 1300 1228 0847 1900 1701 2003 0309 0411 1013 0516 2818 2619 0720 1821 0022 0123 0824 1225 3126 2127 0228
output:
4 2 6 16 20 15 8 9 1 25 7 17 18 22 12 14 11 28 27 21 26 3 5 24 13 31 30 23 19 0 10 29
result:
ok single line: '4 2 6 16 20 15 8 9 1 25 7 17 1... 3 5 24 13 31 30 23 19 0 10 29 '
Test #5:
score: 9.09091
Accepted
time: 1ms
memory: 1824kb
input:
50 0655 1100 0739 1240 3931 2054 0455 2727 1000 3841 4113 4844 3852 2753 0257 2301 0502 1903 0210 3314 4723 1626 4127 2128 2930 0631 1032 0933 4634 3135 1436 1137 3438 2539 2240 3741 3642 3543 4545 0046 2047 2748 1849 0452 4453 3855 1356 0757 3258 0159
output:
1 23 34 32 6 25 41 19 37 9 7 0 10 21 46 26 44 30 47 16 2 33 8 28 20 43 39 40 3 18 35 38 15 24 27 12 13 14 4 49 29 22 31 45 5 11 36 42 17 48
result:
ok single line: '1 23 34 32 6 25 41 19 37 9 7 0...9 29 22 31 45 5 11 36 42 17 48 '
Test #6:
score: 9.09091
Accepted
time: 1ms
memory: 2008kb
input:
50 1756 0436 0207 3028 1331 0530 1213 3125 2910 1349 0754 3055 0956 1957 2758 4101 1615 3920 0421 3222 4023 2624 4225 1726 4727 3728 4929 1330 0031 0332 2233 4834 2135 0736 4537 0638 4439 0240 2541 0542 2443 3444 3545 4346 2947 0148 1949 3650 1251 2352
output:
3 22 38 11 31 40 34 16 19 35 41 18 39 29 21 8 33 10 45 17 9 23 7 32 2 12 0 36 49 46 27 1 28 42 4 43 5 47 24 44 25 15 14 6 20 48 30 13 37 26
result:
ok single line: '3 22 38 11 31 40 34 16 19 35 4...4 25 15 14 6 20 48 30 13 37 26 '
Test #7:
score: 9.09091
Accepted
time: 1ms
memory: 1768kb
input:
60 0022 0158 4500 4532 1700 3623 3400 3737 4344 4600 3102 3204 2707 0508 1910 4711 2513 1814 1615 4116 4217 4018 5519 1020 0721 3622 2823 3024 5825 2926 5727 5128 0329 0830 0131 2432 3333 1234 0635 1736 5637 0038 2139 4340 0241 2642 2243 4844 1345 2346 0947 1448 1149 5350 5051 3752 0453 4554 5455 3456
output:
0 44 7 10 39 20 24 21 15 13 28 27 32 54 40 12 34 41 43 18 17 19 4 49 52 23 31 29 1 30 2 8 56 51 58 35 26 47 53 42 3 59 38 16 57 33 37 11 46 36 50 45 48 6 9 22 55 14 5 25
result:
ok single line: '0 44 7 10 39 20 24 21 15 13 28... 36 50 45 48 6 9 22 55 14 5 25 '
Test #8:
score: 9.09091
Accepted
time: 1ms
memory: 2004kb
input:
60 0300 0459 0200 2733 4728 3943 3200 4502 2744 1100 4120 1640 4400 1637 0400 2102 2506 4707 3410 4011 4113 3515 2916 0319 0621 0122 0823 1624 2225 2326 0227 1028 5429 1930 3331 3032 0533 5834 5335 5736 5237 5138 4239 4940 1241 2842 3243 2744 3945 4446 2647 1448 0049 2050 4851 1152 0953 3854 2455 0756
output:
0 3 44 23 4 13 22 9 28 46 16 41 14 42 55 38 34 12 25 19 18 24 30 56 53 58 51 43 37 36 57 49 5 40 26 29 54 1 6 2 7 8 17 10 47 31 27 32 20 15 33 45 59 39 11 48 50 21 35 52
result:
ok single line: '0 3 44 23 4 13 22 9 28 46 16 4... 33 45 59 39 11 48 50 21 35 52 '
Test #9:
score: 9.09091
Accepted
time: 1ms
memory: 1768kb
input:
60 2000 0300 1817 2812 0715 2933 1859 5130 3700 4200 2136 3800 5204 3216 3500 5905 1809 0610 2913 4014 5015 3216 1017 1319 2020 1721 0323 2324 0425 1426 2827 5728 0729 1230 3031 5832 0833 3634 3435 5536 2237 0138 1639 4240 3141 5142 4843 5244 0045 1946 1147 2148 4649 2650 4951 0252 4353 0954 4455 0556
output:
5 32 21 12 44 22 34 3 18 14 35 20 6 26 24 0 41 53 30 19 9 27 49 46 39 42 56 36 55 45 31 2 52 47 29 1 51 23 25 4 37 58 43 17 28 8 11 7 59 40 48 38 13 33 10 57 16 50 15 54
result:
ok single line: '5 32 21 12 44 22 34 3 18 14 35... 48 38 13 33 10 57 16 50 15 54 '
Test #10:
score: 9.09091
Accepted
time: 1ms
memory: 1820kb
input:
60 1636 0500 0215 0500 4352 0516 0700 3750 1806 3100 4529 2900 3301 4305 2408 5511 5612 4414 2615 0616 1317 3818 0219 0320 0021 5722 4523 4724 5925 0726 3027 1528 5129 0430 5331 0932 3533 0534 3935 3636 2737 0138 1939 3140 1141 1442 4243 2144 2245 4846 0847 1748 4949 2850 3451 2352 4153 1854 5255 5856
output:
9 22 34 43 5 47 49 19 39 27 13 30 26 16 35 4 3 15 33 53 46 21 57 56 59 2 14 12 0 52 29 44 8 55 6 50 24 54 20 23 32 58 40 28 48 45 17 38 37 11 51 42 10 31 25 36 18 41 7 1
result:
ok single line: '9 22 34 43 5 47 49 19 39 27 13...11 51 42 10 31 25 36 18 41 7 1 '
Test #11:
score: 9.09091
Accepted
time: 0ms
memory: 1824kb
input:
60 0200 0017 2541 0115 2929 4300 4538 4454 0500 2004 2606 1808 1009 4010 3611 2212 4213 0814 0015 4716 4917 2418 3819 0920 5321 5222 5823 3324 0125 3926 2127 2928 1229 1130 0331 5032 3433 2534 3735 3036 5537 0738 5739 2840 1341 2742 5143 1444 1745 4346 0247 1648 5649 2350 0451 4852 4153 5954 3155 1956
output:
5 44 24 53 27 15 13 14 54 39 33 41 49 19 23 37 17 51 59 12 10 35 21 50 6 7 1 26 58 20 38 30 47 48 56 9 25 34 22 29 4 52 2 31 46 32 8 45 42 16 57 43 3 36 55 11 18 0 28 40
result:
ok single line: '5 44 24 53 27 15 13 14 54 39 3...16 57 43 3 36 55 11 18 0 28 40 '