제출 #540465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
540465		new_acc	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	40 ms	18280 KiB

shoes

    #include "shoes.h"
    #include<bits/stdc++.h>
    #define fi first
    #define se second
    #define pitem item*
    using namespace std;
    typedef long long ll;
    typedef vector<int> vi;
    typedef vector<ll> vl;
    const int M=1e6+10;
    const int N=1e5+10;
    const int SS=1<<20;
    const int INFi=1e9;
    const ll INFl=1e12;
    int val[N],t[N],seg[(SS<<1)+1],wsk[N];
    bitset<N>vis;
    vi g[N];
    void upd(int a,int ind){
        for(ind+=SS;ind>0;ind>>=1) seg[ind]+=a;
    }
    int Query(int a,int b){
        int res=0;
        for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
            if(!(a&1)) res+=seg[a+1];
            if(b&1) res+=seg[b-1];
        }
        return res;
    }
    ll count_swaps(vi v){
        int n=v.size();
        for(int i=0;i<v.size();i++) t[i+1]=v[i];
        for(int i=1;i<=n;i++)
            if(t[i]>0) g[t[i]].push_back(i);
        for(int i=1;i<=n;i++){
            if(t[i]>0) continue;
            int curr=t[i]*(-1);
            int m=g[curr][wsk[curr]++];
            val[m]=(min(m,i)<<1)+1,val[i]=(min(m,i)<<1);
            vis[max(m,i)]=1;
        }
        ll res=0;
        for(int i=1;i<=n;i++){
            upd(1,val[i]);
            if(vis[i]) res+=(ll)Query(val[i]+1,(n<<1));
        }
        return res;
    }

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

shoes.cpp: In function 'll count_swaps(vi)':
shoes.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for(int i=0;i<v.size();i++) t[i+1]=v[i];
      |                     ~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15