QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #607810 | #7615. Sequence Folding | qiuuu | TL | 3251ms | 21924kb | C++14 | 852b | 2024-10-03 16:30:08 | 2024-10-03 16:30:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100009;
set<LL> st;
map<LL,int> mp0,mp1;
LL n,m,a[N];
int main()
{
//freopen("1.txt","r",stdin);
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)
scanf("%lld",&a[i]),mp0[a[i]]=1,mp1[a[i]]=0,st.insert(min(n-a[i]+1,a[i]));
while(n>1)
{
for(LL i:st)
{
if(!mp1.count(i)) mp1[i]=1;
if(!mp1.count(n-i+1)) mp1[n-i+1]=1;
int tmp1,tmp2;
tmp1=min({mp0[i]+mp0[n-i+1],mp0[i]+mp1[n-i+1]+1,mp1[i]+mp0[n-i+1]+1});
tmp2=min({mp1[i]+mp1[n-i+1],mp0[i]+mp1[n-i+1]+1,mp1[i]+mp0[n-i+1]+1});
mp0[i]=tmp1;
mp1[i]=tmp2;
mp0.erase(n-i+1);
mp1.erase(n-i+1);
}
n/=2,m=0;
for(LL i:st) a[++m]=min(i,n-i+1);
st.clear();
for(int i=1;i<=m;i++) st.insert(a[i]);
}
printf("%d",min(mp0[1],mp1[1]));
}
/*
8 3
1 5 8
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3964kb
input:
8 3 1 5 8
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3904kb
input:
1 1 1
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 2453ms
memory: 21924kb
input:
17179869184 100000 138476 774165 993977 1152277 1236393 1244970 1534017 1693701 1763926 1778781 1842066 1874644 1885666 2120429 2485344 2977941 3158255 3340476 3504862 4000117 4066652 4197639 4338723 4389163 4576965 4761601 5097091 5175412 5295902 5810551 5855982 6001770 6111262 6163309 6351547 6582...
output:
99999
result:
ok single line: '99999'
Test #4:
score: 0
Accepted
time: 3251ms
memory: 21876kb
input:
549755813888 100000 16886305 20807233 27844305 30727441 30898344 35755457 38085835 43336454 47877882 50347884 53237225 53718183 60030541 66954859 80773500 82511603 84025040 86398615 93070876 94502940 98906398 100677488 103720017 105522694 116741042 122492007 135222584 155167916 160926866 166110647 1...
output:
100000
result:
ok single line: '100000'
Test #5:
score: -100
Time Limit Exceeded
input:
17592186044416 100000 44842545 229248515 253567434 347949154 349195610 404810585 639421407 650796923 1019260054 1250861689 1315840401 1318619991 1339387462 1388173647 1406074815 1459749263 1707998226 1902480662 2060860604 2075157570 2410720375 2589192480 2742051226 2784829021 3019629868 3194189913 3...
output:
100000