QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #607703 | #7615. Sequence Folding | qiuuu | WA | 2938ms | 37328kb | C++14 | 869b | 2024-10-03 15:51:36 | 2024-10-03 15:51:38 |
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],cnt;
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)
{
cnt++;
for(int 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(auto 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: 0ms
memory: 3872kb
input:
8 3 1 5 8
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
1 1 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Wrong Answer
time: 2938ms
memory: 37328kb
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:
50168
result:
wrong answer 1st lines differ - expected: '99999', found: '50168'