oj.uz

Submission #718527

# Submission time Handle Problem Language Result Execution time Memory
718527 2023-04-04T09:31:22 Z myrcella Sorting (IOI15_sorting) C++17
20 / 100
 348 ms 404976 KB 
//by szh
#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;
 
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
 
#include "sorting.h"
 
const int maxn = 6e5+10;
 
int n,m;
int a[maxn],b[maxn];
pii ans[maxn];
pii p[maxn];
deque <int> q[maxn];
int id[maxn];
pii pos[maxn];	
map <pii,int> cntt;
vector <pii> nxt1,nxt2;
pii qid[maxn];
 
void update(int x,int y,int val) {
	if (pos[x].fi!=pos[x].se) {
		pii tmp = {min(pos[x].fi,pos[x].se),max(pos[x].fi,pos[x].se)};
		cntt[tmp]+=val;
		int hi = cntt[tmp];
		if (hi==1) nxt1.pb(tmp);
		else if (hi==2) nxt2.pb(tmp);
	}
	if (pos[y].fi!=pos[y].se) {
		pii tmp = {min(pos[y].fi,pos[y].se),max(pos[y].fi,pos[y].se)};
		cntt[tmp]+=val;
		int hi = cntt[tmp];
		if (hi==1) nxt1.pb(tmp);
		else if (hi==2) nxt2.pb(tmp);
	}
}
 
bool check(int cnt) {
	cntt.clear();
	while (!nxt1.empty())nxt1.pop_back();
	while (!nxt2.empty())nxt2.pop_back();
	rep(i,0,n) {
		while (!q[i].empty()) q[i].pop_back();
		q[i].pb(i);
		id[i] = i;
		b[i] = a[i];
	}
	rep(i,0,cnt) {
		int x=p[i].fi,y=p[i].se;
		q[id[x]].pb(y);
		q[id[y]].pb(x);
		swap(id[x],id[y]);
		qid[i] = {id[x],id[y]};
	}
	rep(i,0,n) {
		pos[q[i].back()].fi = q[i].front();
		pos[a[i]].se = i;
	}
	rep(i,0,n) if (pos[i].fi!=pos[i].se) {
		pii tmp = {min(pos[i].fi,pos[i].se),max(pos[i].fi,pos[i].se)};
		cntt[tmp]++;
		if (cntt[tmp]==2) nxt2.pb(tmp);
		else nxt1.pb(tmp);
	}
	rep(i,0,cnt) {
		int x = p[i].fi,y=p[i].se;
		swap(b[x],b[y]);
		update(b[x],b[y],-1);
		pos[b[x]].se = x,pos[b[y]].se = y;
		update(b[x],b[y],1);
		
		update(q[qid[i].fi].back(),q[qid[i].se].back(),-1);
		q[qid[i].fi].pop_front(),q[qid[i].se].pop_front();
		pos[q[qid[i].fi].back()].fi = q[qid[i].fi].front();
		pos[q[qid[i].se].back()].fi = q[qid[i].se].front();
		update(q[qid[i].fi].back(),q[qid[i].se].back(),1);
		
		pii cur = {0,0};
		while (!nxt2.empty() and cntt[nxt2.back()]!=2) nxt2.pop_back();
		while (!nxt1.empty() and cntt[nxt1.back()]!=1) nxt1.pop_back();
		if (!nxt2.empty()) cur = nxt2.back();
		else if (!nxt1.empty()) cur = nxt1.back();
		x = cur.fi,y=cur.se;
		swap(b[x],b[y]);
		update(b[x],b[y],-1);
		pos[b[x]].se = x,pos[b[y]].se = y;
		update(b[x],b[y],1);
		ans[i] = cur;
		while (!nxt2.empty() and cntt[nxt2.back()]!=2) nxt2.pop_back();
		while (!nxt1.empty() and cntt[nxt1.back()]!=1) nxt1.pop_back();
		if (nxt1.empty() and nxt2.empty()) return true;
	}
	return false;
}
 
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N,m= M;
    int l=0,r=M;
    rep(i,0,n) a[i] =S[i];
    rep(i,0,M) p[i] = {X[i],Y[i]};
    while (l<r) {
		int mid=l+r>>1;
		if (check(mid)) r = mid;
		else l = mid+1;
	}
	assert(check(l));
	rep(i,0,l) P[i] = ans[i].fi, Q[i] = ans[i].se;
	return l;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:121:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  121 |   int mid=l+r>>1;
      |           ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 404188 KB Output is correct
2 Correct 251 ms 404288 KB Output is correct
3 Correct 237 ms 404148 KB Output is correct
4 Correct 248 ms 404144 KB Output is correct
5 Correct 242 ms 404200 KB Output is correct
6 Correct 261 ms 404192 KB Output is correct
7 Correct 291 ms 404332 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 404188 KB Output is correct
2 Correct 251 ms 404288 KB Output is correct
3 Correct 237 ms 404148 KB Output is correct
4 Correct 248 ms 404144 KB Output is correct
5 Correct 242 ms 404200 KB Output is correct
6 Correct 261 ms 404192 KB Output is correct
7 Correct 291 ms 404332 KB Output is correct
8 Correct 277 ms 404248 KB Output is correct
9 Correct 267 ms 404264 KB Output is correct
10 Correct 278 ms 404352 KB Output is correct
11 Correct 277 ms 404236 KB Output is correct
12 Correct 274 ms 404248 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 404256 KB Output is correct
2 Correct 257 ms 404252 KB Output is correct
3 Correct 270 ms 404352 KB Output is correct
4 Correct 277 ms 404348 KB Output is correct
5 Correct 251 ms 404304 KB Output is correct
6 Incorrect 240 ms 404380 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 404188 KB Output is correct
2 Correct 251 ms 404288 KB Output is correct
3 Correct 237 ms 404148 KB Output is correct
4 Correct 248 ms 404144 KB Output is correct
5 Correct 242 ms 404200 KB Output is correct
6 Correct 261 ms 404192 KB Output is correct
7 Correct 291 ms 404332 KB Output is correct
8 Correct 277 ms 404248 KB Output is correct
9 Correct 267 ms 404264 KB Output is correct
10 Correct 278 ms 404352 KB Output is correct
11 Correct 277 ms 404236 KB Output is correct
12 Correct 274 ms 404248 KB Output is correct
13 Correct 246 ms 404256 KB Output is correct
14 Correct 257 ms 404252 KB Output is correct
15 Correct 270 ms 404352 KB Output is correct
16 Correct 277 ms 404348 KB Output is correct
17 Correct 251 ms 404304 KB Output is correct
18 Incorrect 240 ms 404380 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 404788 KB Output is correct
2 Correct 300 ms 404668 KB Output is correct
3 Incorrect 348 ms 404976 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 404788 KB Output is correct
2 Correct 300 ms 404668 KB Output is correct
3 Incorrect 348 ms 404976 KB Output isn't correct
4 Halted 0 ms 0 KB -