제출 #368112

#제출 시각아이디문제언어결과실행 시간메모리
368112leinad2Arranging Shoes (IOI19_shoes)C++17
100 / 100
179 ms16108 KiB
#include "shoes.h" #include<bits/stdc++.h> using namespace std; int seg[800010]; void update(int id, int s, int e, int x, int v) { if(e<x||x<s)return; if(s==e) { seg[id]=v; return; } int m=s+e>>1; update(id*2, s, m, x, v); update(id*2+1, m+1, e, x, v); seg[id]=seg[id*2]+seg[id*2+1]; } int get(int id, int s, int e, int l, int r) { if(e<l||r<s)return 0; if(l<=s&&e<=r)return seg[id]; int m=s+e>>1; return get(id*2, s, m, l, r)+get(id*2+1, m+1, e, l, r); } vector<int>v[200010]; long long count_swaps(vector<int>s) { long long ans=0; int i, j; int n=s.size()/2; for(i=0;i<s.size();i++) { if(s[i]>0)v[s[i]].push_back(i); else v[-s[i]+n].push_back(i); } for(i=0;i++<2*n;)reverse(v[i].begin(), v[i].end()); for(i=0;i<s.size();i++) { if(get(1, 1, 2*n, i+1, i+1))continue; if(s[i]>0)v[s[i]].pop_back(),ans++; else v[-s[i]+n].pop_back(); if(s[i]>0) { j=v[s[i]+n].back(); v[s[i]+n].pop_back(); } else { j=v[-s[i]].back(); v[-s[i]].pop_back(); } //printf("%d %d\n", i, j); ans+=(j-i-1); ans-=get(1, 1, 2*n, i+2, j+1); update(1, 1, 2*n, j+1, 1); } return ans; }

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

shoes.cpp: In function 'void update(int, int, int, int, int)':
shoes.cpp:13:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |     int m=s+e>>1;
      |           ~^~
shoes.cpp: In function 'int get(int, int, int, int, int)':
shoes.cpp:22:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     int m=s+e>>1;
      |           ~^~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:31:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(i=0;i<s.size();i++)
      |             ~^~~~~~~~~
shoes.cpp:37:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(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...