Submission #849984

#	Time	Username	Problem	Language	Result	Execution time	Memory
849984		tosivanmak	Arranging Shoes (IOI19_shoes)	C++17	Compilation error	0 ms	0 KiB

shoes

#include<bits/stdc++.h>
using namespace std;
#define ll long long

struct pairs{
   ll l,r;
   bool operator<(const pairs& p)const{
    //    l,r,p.l,p.r
       ll cnt=0;
      if(r<l){
           cnt++;
       }
        if(p.l<l){
           cnt++;
       }
        if(p.l<r){
           cnt++;
       }
        if(p.r<l){
           cnt++;
       }
        if(p.r<r){
           cnt++;
       }
        if(p.r<p.l){
           cnt++;
       }
       ll cnt2=0;
    //    p.l,p.r,l,r
       if(p.r<p.l){
           cnt2++;
       }
        if(l<p.l){
           cnt2++;
       }
        if(l<p.r){
           cnt2++;
       }
        if(r<p.l){
           cnt2++;
       }
        if(r<p.r){
           cnt2++;
       }
        if(r<l){
           cnt2++;
       }
    //    cout<<1;
    return cnt<=cnt2;
   }
};
 vector<pairs>bruh;
 void merge(ll l, ll r){
     ll mid=(l+r)>>1;
     ll ptr=l,ptr2=mid+1;
     vector<pairs>get;
     for(int i=l;i<=r;i++){
         if(ptr==mid+1){
             get.push_back(bruh[ptr2]);
             ptr2++;
         }
         else if(ptr2==r+1){
             get.push_back(bruh[ptr]);
             ptr++;
         }
      else if(bruh[ptr]<bruh[ptr2]){
          get.push_back(bruh[ptr]);
          ptr++;
       }
       else{
           get.push_back(bruh[ptr2]);
           ptr2++;
       }
     }
     for(int i=l;i<=r;i++){
         bruh[i]=get[i-l];
     }
 }
void merge_sort(ll l, ll r){
    if(l==r){
       return;
    }
    ll mid=(l+r)>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    merge(l,r);
}

struct FEN{
     vector<ll>fen;
     void init(ll n){
         fen.resize(n+5);
         for(int i=0;i<=n+4;i++){
             fen[i]=0;
         }
     }
     void upd(ll n, ll m, ll val){
         for(int i=n;i<=m;i+=i&(-i)){
             fen[i]+=val;
            //  cout<<i;
         }
     }
     ll sum(ll e){
         ll su=0;
         while(e>=1){
             su+=fen[e];
             e-=e&(-e);
         }
        //  cout<<1;
         return su;
     }
}f;
vector<int>adj[1000005],adj2[1000005]; int ptr[1000005];
long long count_swaps(std::vector<int> s) {

       
     vector<ll>make;
    ll why=s.size();
       
     for(int i=0;i<why;i++){
         if(s[i]<0){
             make.push_back(-(s[i]));
             adj[-(s[i])].push_back(i+1);
         }
         else{
             adj2[s[i]].push_back(i+1);
         }
     }
    
  
     for(int i=0;i<=why+4;i++){
         ptr[i]=0;
     }
     
    
    //  for(auto u: adj[2]){
    //      cout<<u<<" ";
    //  }
    ll siz=make.size();
     for(int i=0;i<siz;i++){

         bruh.push_back({adj[make[i]][ptr[make[i]]],adj2[make[i]][ptr[make[i]]]});
         ptr[make[i]]++;
     }
    //  sort(bruh.begin(),bruh.end());
    // for(int i=0;i<bruh.size();i++){
    //     for(int j=0;j<bruh.size()-1;j++){
    //         if(bruh[j+1]<bruh[j]){
    //             swap(bruh[j],bruh[j+1]);
    //         }
    //     }
    // }
    merge_sort(0,bruh.size()-1);
      
     vector<ll>real;
     ll siz2=bruh.size();
     
     for(int i=0;i<siz2;i++){
        real.push_back(bruh[i].l);
        real.push_back(bruh[i].r);
     }
     
    //  for(auto u: real){
    //      cout<<u<<" ";
    //  }
     f.init(300000);
     ll ans=0;
     ll siz3=real.size();
     for(int i=0;i<siz3;i++){
         ans+=f.sum(300000)-f.sum(real[i]);
        //  cout<<f.sum(200000)<<" "<<real[i]<<" ";
        //  cout<<f.sum(real[i])<<"\n";
         f.upd(real[i],300000,1);
     }
     return ans;
    // return 0;
}

// #ifndef ONLINE_JUDGE
  int main() {
	int n;
	cin>>n;
	vector<int> S(2 * n);
	for (int i = 0; i < 2 * n; i++){
		cin>>S[i];
    }
	long long result = count_swaps(S);

    cout<<result<<"\n";
	return 0;
}
// #endif

Compilation message (stderr)

/usr/bin/ld: /tmp/ccCx1hbt.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccVUDq3s.o:shoes.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status