Submission #988949

#TimeUsernameProblemLanguageResultExecution timeMemory
988949emptypringlescanArchery (IOI09_archery)C++17
2 / 100
2098 ms672 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") int n; long long r; int arr[10005],brr[10005],at; int calc(){ if(arr[at]==1) return 1; for(int i=0; i<2*n; i++) brr[i]=arr[i]; int ex[n]; memset(ex,0,sizeof(ex)); int rnd=min(n,400); for(int k=0; k<rnd; k++){ for(int j=0; j<n; j++) ex[j]=0; if(brr[1]>brr[0]) ex[0]=1; for(int j=1; j<n; j++){ if(brr[j<<1|1]<brr[j<<1]) ex[j]=1; } swap(brr[ex[0]],brr[(n-1)<<1|ex[n-1]]); for(int i=0; i<n-2; i++){ swap(brr[i<<1|ex[i]],brr[(i+1)<<1|ex[i+1]]); } } int cur=0; for(int i=0; i<2*n; i++){ if(arr[at]==brr[i]) cur=i/2; } if(arr[at]>n) return cur+1; cur-=r-rnd; cur%=n; if(cur<0) cur+=n; return cur+1; } int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> r; for(int i=0; i<2*n; i++){ cin >> arr[i]; } for(int i=0; i<2*n-1; i++) swap(arr[i],arr[i+1]); at=2*n-1; pair<int,int> ans={1e8,-1}; for(int i=2*n-1; i>=max(0,2*n-4000); i-=2){ int x=calc(); //cout << i << ' ' << x << '\n'; if(x<ans.first) ans={x,i}; if(i){ at--; swap(arr[i],arr[i-1]); at--; swap(arr[i-1],arr[i-2]); at--; } } cout << ans.second/2+1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...