제출 #339748

#제출 시각아이디문제언어결과실행 시간메모리
339748wwddCheerleaders (info1cup20_cheerleaders)C++14
54 / 100
1122 ms32168 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pl; typedef vector<ll> vl; const ll INFL = 1e18; vl w; vl wa,wi; void shuf(int n) { vl x(w.size(),0); for(int i=0;i<w.size();i++) { int nx = (i>>1) + ((i&1)<<(n-1)); x[nx] = w[i]; } w = x; wa.assign(n,0); wi.assign(n,-1); } void proc(int n) { vector<vl> wo[2] = {{w.size(),vl()},{w.size(),vl()}}; int cu = 0; for(int i=0;i<w.size();i++) { wo[cu][i].push_back(w[i]); } for(int k=0;k<n;k++) { ll res[2] = {0,0}; int nu = 1-cu; for(int i=0;i<w.size();i+=(1<<(k+1))) { for(int j=0;j<2;j++) { int pt = 0; for(int l=0;l<wo[cu][i^(j<<k)].size();l++) { while(pt < wo[cu][i^((1^j)<<k)].size() && wo[cu][i^((1^j)<<k)][pt] < wo[cu][i^(j<<k)][l]) { pt++; } res[j] += pt; } } wo[nu][i].resize((1<<(k+1))); merge(wo[cu][i].begin(),wo[cu][i].end(), wo[cu][i+(1<<k)].begin(),wo[cu][i+(1<<k)].end(), wo[nu][i].begin()); } wa[k] = min(res[0],res[1]); wi[k] = res[0] > res[1]; cu = nu; } } int main() { ios::sync_with_stdio(0);cin.tie(0); ll n; cin >> n; ll m = 1<<n; wa.assign(n,0); wi.assign(n,-1); for(int i=0;i<m;i++) { ll t; cin >> t; w.push_back(t); } if(n == 0) { cout << 0 << '\n'; cout << 2 << '\n'; return 0; } ll ma = INFL; pl st = {0,0}; for(int i=0;i<n;i++) { ll res = 0; ll rb = 0; proc(n); for(int j=0;j<n;j++) { res += wa[j]; rb |= wi[j]<<j; } if(res < ma) { ma = res; st = {i,rb}; } shuf(n); } cout << ma << '\n'; for(int i=0;i<st.first;i++) { cout << "2"; } st.second = (st.second<<1)|((st.second&(1<<(n-1))>>(n-1))); for(int i=0;i<n;i++) { if((st.second)&(1<<i)) { cout << "1"; } cout << "2"; } cout << '\n'; }

컴파일 시 표준 에러 (stderr) 메시지

cheerleaders.cpp: In function 'void shuf(int)':
cheerleaders.cpp:11:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int i=0;i<w.size();i++) {
      |              ~^~~~~~~~~
cheerleaders.cpp: In function 'void proc(int)':
cheerleaders.cpp:22:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i=0;i<w.size();i++) {
      |              ~^~~~~~~~~
cheerleaders.cpp:28:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int i=0;i<w.size();i+=(1<<(k+1))) {
      |               ~^~~~~~~~~
cheerleaders.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int l=0;l<wo[cu][i^(j<<k)].size();l++) {
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~~
cheerleaders.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |      while(pt < wo[cu][i^((1^j)<<k)].size() && wo[cu][i^((1^j)<<k)][pt] < wo[cu][i^(j<<k)][l]) {
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...