oj.uz

Submission #718537

# Submission time Handle Problem Language Result Execution time Memory
718537 2023-04-04T09:45:54 Z oolimry Sorting (IOI15_sorting) C++17
74 / 100
 283 ms 304440 KB 
#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 = 2e5+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];	
vector <pair<int,pii>> nxt;
pii qid[maxn];
 
void update(int x,int y,int val) {
	if (pos[x].fi!=pos[x].se) nxt.pb({x,pos[x]});
	if (pos[y].fi!=pos[y].se) nxt.pb({y,pos[y]});
}
 
bool check(int cnt) {
	while (!nxt.empty())nxt.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) {
		nxt.pb({i,pos[i]});
	}
	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 (!nxt.empty() and pos[nxt.back().fi]!=nxt.back().se) nxt.pop_back();
		if(!nxt.empty()) cur = nxt.back().se;
		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 (!nxt.empty() and pos[nxt.back().fi]!=nxt.back().se) nxt.pop_back();
	return nxt.empty();
}
 
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 'void update(int, int, int)':
sorting.cpp:39:29: warning: unused parameter 'val' [-Wunused-parameter]
   39 | void update(int x,int y,int val) {
      |                         ~~~~^~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:99:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |   int mid=l+r>>1;
      |           ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 134948 KB Output is correct
2 Correct 102 ms 134904 KB Output is correct
3 Correct 81 ms 134872 KB Output is correct
4 Correct 87 ms 134972 KB Output is correct
5 Correct 84 ms 134880 KB Output is correct
6 Correct 85 ms 134972 KB Output is correct
7 Correct 84 ms 134928 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 134948 KB Output is correct
2 Correct 102 ms 134904 KB Output is correct
3 Correct 81 ms 134872 KB Output is correct
4 Correct 87 ms 134972 KB Output is correct
5 Correct 84 ms 134880 KB Output is correct
6 Correct 85 ms 134972 KB Output is correct
7 Correct 84 ms 134928 KB Output is correct
8 Correct 89 ms 134852 KB Output is correct
9 Correct 86 ms 134976 KB Output is correct
10 Correct 104 ms 134988 KB Output is correct
11 Correct 85 ms 135000 KB Output is correct
12 Correct 84 ms 135024 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 135036 KB Output is correct
2 Correct 90 ms 134980 KB Output is correct
3 Correct 85 ms 134996 KB Output is correct
4 Correct 84 ms 134988 KB Output is correct
5 Correct 81 ms 135000 KB Output is correct
6 Correct 90 ms 134976 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 134948 KB Output is correct
2 Correct 102 ms 134904 KB Output is correct
3 Correct 81 ms 134872 KB Output is correct
4 Correct 87 ms 134972 KB Output is correct
5 Correct 84 ms 134880 KB Output is correct
6 Correct 85 ms 134972 KB Output is correct
7 Correct 84 ms 134928 KB Output is correct
8 Correct 89 ms 134852 KB Output is correct
9 Correct 86 ms 134976 KB Output is correct
10 Correct 104 ms 134988 KB Output is correct
11 Correct 85 ms 135000 KB Output is correct
12 Correct 84 ms 135024 KB Output is correct
13 Correct 85 ms 135036 KB Output is correct
14 Correct 90 ms 134980 KB Output is correct
15 Correct 85 ms 134996 KB Output is correct
16 Correct 84 ms 134988 KB Output is correct
17 Correct 81 ms 135000 KB Output is correct
18 Correct 90 ms 134976 KB Output is correct
19 Correct 84 ms 134864 KB Output is correct
20 Correct 83 ms 134972 KB Output is correct
21 Correct 96 ms 135356 KB Output is correct
22 Correct 90 ms 135536 KB Output is correct
23 Correct 100 ms 135404 KB Output is correct
24 Correct 99 ms 135408 KB Output is correct
25 Correct 90 ms 135260 KB Output is correct
26 Correct 105 ms 135368 KB Output is correct
27 Correct 85 ms 135400 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 135404 KB Output is correct
2 Correct 103 ms 135344 KB Output is correct
3 Correct 99 ms 135424 KB Output is correct
4 Correct 91 ms 135452 KB Output is correct
5 Correct 89 ms 135624 KB Output is correct
6 Correct 92 ms 135424 KB Output is correct
7 Correct 101 ms 135640 KB Output is correct
8 Correct 111 ms 135568 KB Output is correct
9 Correct 98 ms 135668 KB Output is correct
10 Correct 96 ms 135564 KB Output is correct
11 Correct 88 ms 135452 KB Output is correct
12 Correct 109 ms 135496 KB Output is correct
13 Correct 87 ms 135632 KB Output is correct
14 Correct 89 ms 135164 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 135404 KB Output is correct
2 Correct 103 ms 135344 KB Output is correct
3 Correct 99 ms 135424 KB Output is correct
4 Correct 91 ms 135452 KB Output is correct
5 Correct 89 ms 135624 KB Output is correct
6 Correct 92 ms 135424 KB Output is correct
7 Correct 101 ms 135640 KB Output is correct
8 Correct 111 ms 135568 KB Output is correct
9 Correct 98 ms 135668 KB Output is correct
10 Correct 96 ms 135564 KB Output is correct
11 Correct 88 ms 135452 KB Output is correct
12 Correct 109 ms 135496 KB Output is correct
13 Correct 87 ms 135632 KB Output is correct
14 Correct 89 ms 135164 KB Output is correct
15 Runtime error 283 ms 304440 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -