Submission #155761

#	Time	Username	Problem	Language	Result	Execution time	Memory
155761		gurkot	Arranging Shoes (IOI19_shoes)	C++14	Compilation error	0 ms	0 KiB

shoes

#include <cstdio>
#include <cassert>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;

struct Q{int x,npair;};
queue <Q> q[200001];
Q qin,qout;

int n;
int s[200001];

int prev(int u){
 return u&(u-1);    
}

int next(int u){
 return (u<<1)-(u&(u-1));
}

int getsum(int a, int b){
 if (a>b) return 0;
 int ans=0;
 while (b>0){
  ans+=s[b];  b=prev(b);
 }    
 a--;
 while (a>0){
  ans-=s[a];  a=prev(a);
 }    
 return ans;
}

void update(int pos, int x){
 while (pos<=n){
  s[pos]+=x;  pos=next(pos);
 }     
}

long long count_swaps(std::vector<int> a) {
 long long ans=0;
 int x,mx,npair=0;
 n=a.size();
 for (int i=0;i<n;i++){
  x=mx=a[i]; if (mx<0) mx=-mx;
  if (q[mx].size()==0) {
    npair++;
    qin.x=x; qin.npair=npair;
    q[mx].push(qin);
    update(npair,1);
    //cout<<"i="<<i<<"  update "<<npair<<"<=1"<<endl;
  } else {
   qout=q[mx].front();
   if (qout.x==x) {
    npair++;
    qin.x=x; qin.npair=npair;
    q[mx].push(qin);
    update(npair,1);                  
    //cout<<"i="<<i<<"  update (same x) "<<npair<<"<=1"<<endl;
   } else {
    int old_npair=qout.npair;    
    ans+=getsum(old_npair+1,npair);
    if (x<0) ans++;
    update(old_npair,1);          
    //cout<<"i="<<i<<"  update oldpair (same x) "<<old_npair<<"<=+1(2)"<<endl;    
    q[mx].pop();
   }        
  }//size()>0       
 }//i 
 return ans;	
}

int main() {
	int n;
	//freopen("3-18.in","r",stdin);
	//freopen("shoes.out","w",stdout);
	assert(1 == scanf("%d", &n));
	vector<int> S(2 * n);
	for (int i = 0; i < 2 * n; i++)        
		assert(1 == scanf("%d", &S[i]));
	fclose(stdin);
  
	long long result = count_swaps(S);
	printf("%lld\n", result);

    fclose(stdout);
	return 0;
}

Compilation message (stderr)

/tmp/ccNgpmwr.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cchvOqRF.o:shoes.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status