제출 #138563

#제출 시각아이디문제언어결과실행 시간메모리
138563almogwald고대 책들 (IOI17_books)C++14
0 / 100
2037 ms376 KiB
#include <utility> #include <algorithm> #include <math.h> #include <vector> #include "books.h" #define fori(i,n) for(int i=0;i<n;i++) #define forib(i,n) for(int i=n-1;i>=0;i--) #define maxl 10000000000 typedef long long lol; using namespace std; typedef vector<int> veci; lol sum=0; veci merge(veci a ,veci b){ int i=0,j=0; veci ans; while(i<a.size()&&j<b.size()){ if(a[i]<b[j]){ ans.push_back(a[i++]); sum+=j; }else{ ans.push_back(b[j++]); } } while(i<a.size()){ ans.push_back(a[i++]); sum+=j; } while(j<b.size()){ ans.push_back(b[j++]); } return ans; } veci mergesort(veci a){ if(a.size()==1){ return a; } veci b,c; fori(i,a.size()){ if(i<a.size()/2){ b.push_back(a[i]); }else{ c.push_back(a[i]); } } b=mergesort(b); c=mergesort(c); return merge(b,c); } long long minimum_walk(vector<int> p, int s) { int n=p.size(); vector<int> a(n,-1); int cur=s; do{ sum+=abs(p[cur]-cur); cur= p[cur]; a[cur]=0; }while(cur !=s); int num=1; vector<int> b(n+1,s); int mon=-1; fori(i,n){ if(p[i]==i||a[i]!=-1){ continue; } int l=-10000000; int r=n; int cur=i; do{ if(cur<s){ l=max(l,cur); }else{ r=min(r,cur); } sum+=abs(p[cur]-cur); cur= p[cur]; a[cur]=num; }while(cur !=i); num++; b[r-1]=l; } bool ok=false; int l=s+1;int r=s; while(l!=0 || r!=n-1){ mon++; int ll=l; int rr=r; if(l!=0){ l--; ll--; cur=p[l]; if(cur<s){ ll=min(ll,cur); }else{ rr=max(rr,cur); } }else{ r++; rr++; cur=p[r]; if(cur<s){ ll=min(ll,cur); }else{ rr=max(rr,cur); } } while(ll!=l|| r!=rr){ while(r<rr){ r++; cur=p[r]; if(cur<s){ ll=min(ll,cur); }else{ rr=max(rr,cur); } } while(r<rr){ l--; cur=p[l]; if(cur<s){ ll=min(ll,cur); }else{ rr=max(rr,cur); } } } } return sum+mon*2; }

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

books.cpp: In function 'veci merge(veci, veci)':
books.cpp:17:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<a.size()&&j<b.size()){
        ~^~~~~~~~~
books.cpp:17:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<a.size()&&j<b.size()){
                    ~^~~~~~~~~
books.cpp:25:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<a.size()){
        ~^~~~~~~~~
books.cpp:29:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(j<b.size()){
        ~^~~~~~~~~
books.cpp: In function 'veci mergesort(veci)':
books.cpp:6:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(i,n) for(int i=0;i<n;i++)
books.cpp:39:7:
  fori(i,a.size()){
       ~~~~~~~~~~                
books.cpp:39:2: note: in expansion of macro 'fori'
  fori(i,a.size()){
  ^~~~
books.cpp:40:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i<a.size()/2){
      ~^~~~~~~~~~~
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:82:7: warning: unused variable 'ok' [-Wunused-variable]
  bool ok=false;
       ^~
#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...