제출 #476918

#제출 시각아이디문제언어결과실행 시간메모리
476918ponytailArranging Shoes (IOI19_shoes)C++17
100 / 100
329 ms78016 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; typedef long long ll; mt19937 rng((int)std::chrono::steady_clock::now().time_since_epoch().count()); int bit[2 * MAXN]; void add(int x, int v) { for(;x<2 * MAXN;x+=x&-x) bit[x] += v; } int sum(int x) { int s= 0; for(;x;x-=x&-x) s += bit[x]; return s; } ll count_swaps(vector<int> S) { for(int i=0; i<2 * MAXN; i++) bit[i] = 0; ll ans = 0; map<int, queue<int> >mp; for(int i=0; i<S.size(); i++) { if(S[i] < 0) { mp[-S[i]].push(i); } } int partner[S.size()]; for(int i=0; i<S.size(); i++) { if(S[i] > 0) { partner[i] = mp[S[i]].front(); partner[mp[S[i]].front()] = i; mp[S[i]].pop(); } } vector<pair<int, int> > v; for(int i=0; i<S.size(); i++) { if(S[i] > 0) { if(partner[i] > i) { v.push_back({partner[i] + i, i}); } else { v.push_back({partner[i] + i - 1, i}); } } } sort(v.begin(), v.end()); int lb = 0; for(pair<int, int> x: v) { int me = x.second + sum(2 * MAXN - 1) - sum(x.second + 1); int pe = partner[x.second] + sum(2 * MAXN - 1) - sum(partner[x.second] + 1); ans += (partner[x.second] > x.second ? me + pe : me + pe - 1) - 2 * lb; lb += 2; add(x.second + 1, 1); add(partner[x.second] + 1, 1); } return ans; }

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

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0; i<S.size(); i++) {
      |                  ~^~~~~~~~~
shoes.cpp:26:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=0; i<S.size(); i++) {
      |                  ~^~~~~~~~~
shoes.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0; i<S.size(); i++) {
      |                  ~^~~~~~~~~
#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...