Submission #439846

#TimeUsernameProblemLanguageResultExecution timeMemory
439846adamjinweiArranging Shoes (IOI19_shoes)C++14
100 / 100
139 ms73480 KiB
#include <bits/stdc++.h> #include "shoes.h" #define inf 1000000007 #define mod 1000000007 #define lowbit(x) (x&(-x)) #define rnd() rand_num() #define bigrnd() dis(rand_num) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") //#define int long long using namespace std; unsigned sed=std::chrono::system_clock::now().time_since_epoch().count(); mt19937 rand_num(sed); uniform_int_distribution<long long> dis(0,inf); template <typename T> void read(T &x){ x=0;char ch=getchar();int fh=1; while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();} while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); x*=fh; } template <typename T> void write(T x) { if (x<0) x=-x,putchar('-'); if (x>9) write(x/10); putchar(x%10+'0'); } template <typename T> void writeln(T x) { write(x); puts(""); } int n; int a[200005]; int b[200005]; int bit[200005]; bool vis[200005]; queue<int> q[100005]; void modify(int x,int y) { while(x<=2*n) { bit[x]+=y; x+=lowbit(x); } } int query(int x) { int res=0; while(x) { res+=bit[x]; x-=lowbit(x); } return res; } long long count_swaps(vector<int> s) { n=s.size()/2; for(int i=1;i<=2*n;++i) { a[i]=s[i-1]; if(a[i]<0) q[-a[i]].push(i); } long long ans=0; for(int i=1;i<=2*n;++i) if(a[i]>0) { b[i]=q[a[i]].front(); b[q[a[i]].front()]=i; if(i<q[a[i]].front()) ans++; q[a[i]].pop(); } for(int i=1;i<=2*n;++i) modify(i,1); for(int i=1;i<=2*n;++i) { if(vis[i]) continue; ans+=query(b[i]-1)-query(i); modify(b[i],-1); modify(i,-1); vis[i]=vis[b[i]]=1; } return ans; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...