Submission #967376

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
967376	2024-04-22T03:36:15 Z	lsi	Arranging Shoes (IOI19_shoes)	C++14	Compilation error	0 ms	0 KB

shoes

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

typedef long long ll;
int nm[200100];
bool taken[200100];
int pir[200100];
vector<int> l[200100],r[200100];
int tre[200100];

int lowbit(int i){
	return i&(-i);
}

int ct(int p){
	int tp=0;
	for (int i=p;i;i-=lowbit(i)){
		tp+=tre[i];
	}
	return tp;
}

void ad(int p){
	for (int i=p;i<=200100;i+=lowbit(i)){
		tre[i]++;
	}
}

int main(){
	ll ans=0;
	memset(taken,false,sizeof taken);
	int n; scanf("%d",&n);
	for (int i=1;i<=n*2;i++){
		scanf("%d",&nm[i]);
		int tp=nm[i];
		if (tp<0) tp*=-1;
		if (nm[i]<0){
			if (!r[tp].empty()){
				pir[i]=r[tp][0];
				pir[r[tp][0]]=i;
				r[tp].erase(r[tp].begin());
				continue;
			}
			l[tp].push_back(i);
		}else{
			if (!l[tp].empty()){
				pir[i]=l[tp][0];
				pir[l[tp][0]]=i;
				l[tp].erase(l[tp].begin());
				continue;
			}
			r[tp].push_back(i);
		}
	}
	for (int i=1;i<=n*2;i++){
		if (taken[i]) continue;
		int tp,tpa=0;
		if (nm[i]>0){
			tpa+=1;
		}
		tp=pir[i];
		tpa+=tp-i-1;
		tpa-=ct(tp-1)-ct(i);
		taken[tp]=true;
		ad(tp);
		ans+=tpa;
		//printf("%d %d\n",tp,tpa);
	}
	printf("%lld",ans);
}

Compilation message

shoes.cpp: In function 'int main()':
shoes.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  int n; scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
shoes.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%d",&nm[i]);
      |   ~~~~~^~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccBxwapB.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc8qCTAx.o:shoes.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccBxwapB.o: in function `main':
grader.cpp:(.text.startup+0x29d): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status