Last active
December 7, 2020 22:31
-
-
Save cgiosy/2ff5f6f21f642a6b25aee444eefe4aca to your computer and use it in GitHub Desktop.
19849. 문제지 나르기
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#pragma GCC optimize("O3") | |
#pragma GCC target("avx2") | |
#include <bits/stdc++.h> | |
#define R(i,n) for(int i=0; i<n; i++) | |
using namespace std; | |
int main() { | |
ios::sync_with_stdio(0);cin.tie(0); | |
int N, Q; | |
cin>>N>>Q; | |
alignas(32) long X[2048]; | |
memset(X, 63, 16384); | |
R(k, N+Q) { | |
alignas(32) long Y[2048], a[11]; | |
R(i, 11) cin>>a[i]; | |
Y[0]=0; | |
R(i, 11) Y[0]-=a[i]; | |
R(i, 11) a[i]*=2; | |
R(i, 11) R(j, 1<<i) Y[j+(1<<i)]=Y[j]+a[i]; | |
if(k<N) { | |
R(i, 2048) X[i]=min(X[i], Y[i]); | |
} else { | |
long m=0; | |
R(i, 2048) m=max(m, Y[i]-X[i]); | |
cout<<m<<'\n'; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
풀이:
dist(x, y)
에서x[i] > y[i]
이면x[i] - y[i]
이고,x[i] < y[i]
이면-x[i] + y[i]
이므로, 상태가 정해져 있다면x
와y
를 분리해서 생각할 수 있다.i
가 11가지밖에 안 되니, 각i
에 대해x[i] > y[i]
인 상태를 비트로 표현해서 생각하면 어떨까?x[i]
와y[i]
모두 음수가 되어 결과적으로 관계가 맞을 때보다 거리가 감소한다. 그런데 우리는 최댓값을 구해야 하므로, 실제 대소관계를 생각할 필요가 없다!SIMD
__builtin_ctz
나__builtin_clz
, 혹은i&-i
를 쓰는 등 최하위/최상위 비트를 직접 구한다면 영 쉽지가 않다. 따라서, 위 코드는 아래 부분이 핵심이다.i
를 고정해놓고i
번 비트가 꺼진 곳(j
)을 이용하여 켜진 곳(j+(1<<i)
)을 업데이트해 준다.|
과+
이 동일한 결과를 낸다는 것이 보장되어 있을 경우,+
를 사용해야 컴파일러에게 더 직접적으로 힌트를 줄 수 있다.