제출 #1072049

#제출 시각아이디문제언어결과실행 시간메모리
1072049PikachudoraEHEArranging Shoes (IOI19_shoes)C++14
100 / 100
132 ms141672 KiB
#include "shoes.h" #include<bits/stdc++.h> #define ll long long using namespace std; const int N = 2e5+5; const int OFFSET = 1e5; int n; int a[N],chk[N]; queue<int>q[N]; struct fenwick{ int f[N]; void update(int idx,int v){ for(int i=idx;i<N;i+=i&-i){ f[i]+=v; } return; } int sum(int idx){ int s=0; for(int i=idx;i>0;i-=i&-i){ s+=f[i]; } return s; } }f,f2; long long count_swaps(std::vector<int> s){ for(int i=1;i<=s.size();i++){a[i]=s[i-1];f.update(i,1);} ll ans=0;ll n = s.size(); for(int i=1;i<=n;i++){ if(a[i]<0){ q[OFFSET-a[i]].push(i); } else{ q[a[i]].push(i); } } for(int i=1;i<=n;i++){ if(chk[i])continue;int ii; if(a[i]<0){ ii = q[(-1)*a[i]].front(); q[(-1)*a[i]].pop(); q[OFFSET-a[i]].pop(); chk[ii]=1; ans+=f.sum(ii)-f.sum(i)-1; } else{ ii = q[OFFSET+a[i]].front(); q[OFFSET+a[i]].pop(); q[a[i]].pop(); chk[ii]=1; ans+=f.sum(ii)-f.sum(i); } f.update(ii,-1);f.update(i,-1); } return ans; }

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

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=1;i<=s.size();i++){a[i]=s[i-1];f.update(i,1);}
      |                 ~^~~~~~~~~~
shoes.cpp:38:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   38 |         if(chk[i])continue;int ii;
      |         ^~
shoes.cpp:38:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   38 |         if(chk[i])continue;int ii;
      |                            ^~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...