oj.uz

Submission #718540

# Submission time Handle Problem Language Result Execution time Memory
718540 2023-04-04T09:48:45 Z oolimry Sorting (IOI15_sorting) C++17
74 / 100
 1000 ms 298992 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 = 4e5+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 174 ms 269612 KB Output is correct
2 Correct 162 ms 269536 KB Output is correct
3 Correct 159 ms 269708 KB Output is correct
4 Correct 157 ms 269492 KB Output is correct
5 Correct 156 ms 269516 KB Output is correct
6 Correct 158 ms 269496 KB Output is correct
7 Correct 162 ms 269624 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 269612 KB Output is correct
2 Correct 162 ms 269536 KB Output is correct
3 Correct 159 ms 269708 KB Output is correct
4 Correct 157 ms 269492 KB Output is correct
5 Correct 156 ms 269516 KB Output is correct
6 Correct 158 ms 269496 KB Output is correct
7 Correct 162 ms 269624 KB Output is correct
8 Correct 155 ms 269636 KB Output is correct
9 Correct 157 ms 269696 KB Output is correct
10 Correct 157 ms 269716 KB Output is correct
11 Correct 156 ms 269644 KB Output is correct
12 Correct 158 ms 269712 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 269564 KB Output is correct
2 Correct 162 ms 269596 KB Output is correct
3 Correct 159 ms 269716 KB Output is correct
4 Correct 159 ms 269756 KB Output is correct
5 Correct 160 ms 269612 KB Output is correct
6 Correct 161 ms 269616 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 269612 KB Output is correct
2 Correct 162 ms 269536 KB Output is correct
3 Correct 159 ms 269708 KB Output is correct
4 Correct 157 ms 269492 KB Output is correct
5 Correct 156 ms 269516 KB Output is correct
6 Correct 158 ms 269496 KB Output is correct
7 Correct 162 ms 269624 KB Output is correct
8 Correct 155 ms 269636 KB Output is correct
9 Correct 157 ms 269696 KB Output is correct
10 Correct 157 ms 269716 KB Output is correct
11 Correct 156 ms 269644 KB Output is correct
12 Correct 158 ms 269712 KB Output is correct
13 Correct 183 ms 269564 KB Output is correct
14 Correct 162 ms 269596 KB Output is correct
15 Correct 159 ms 269716 KB Output is correct
16 Correct 159 ms 269756 KB Output is correct
17 Correct 160 ms 269612 KB Output is correct
18 Correct 161 ms 269616 KB Output is correct
19 Correct 156 ms 269620 KB Output is correct
20 Correct 161 ms 269560 KB Output is correct
21 Correct 166 ms 270080 KB Output is correct
22 Correct 159 ms 270116 KB Output is correct
23 Correct 159 ms 270160 KB Output is correct
24 Correct 161 ms 270128 KB Output is correct
25 Correct 160 ms 269904 KB Output is correct
26 Correct 165 ms 270008 KB Output is correct
27 Correct 165 ms 270268 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 270016 KB Output is correct
2 Correct 163 ms 270032 KB Output is correct
3 Correct 162 ms 270060 KB Output is correct
4 Correct 164 ms 270104 KB Output is correct
5 Correct 163 ms 270324 KB Output is correct
6 Correct 161 ms 270148 KB Output is correct
7 Correct 166 ms 270336 KB Output is correct
8 Correct 164 ms 270260 KB Output is correct
9 Correct 161 ms 270208 KB Output is correct
10 Correct 167 ms 270320 KB Output is correct
11 Correct 165 ms 270036 KB Output is correct
12 Correct 167 ms 270040 KB Output is correct
13 Correct 168 ms 270352 KB Output is correct
14 Correct 159 ms 269920 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 270016 KB Output is correct
2 Correct 163 ms 270032 KB Output is correct
3 Correct 162 ms 270060 KB Output is correct
4 Correct 164 ms 270104 KB Output is correct
5 Correct 163 ms 270324 KB Output is correct
6 Correct 161 ms 270148 KB Output is correct
7 Correct 166 ms 270336 KB Output is correct
8 Correct 164 ms 270260 KB Output is correct
9 Correct 161 ms 270208 KB Output is correct
10 Correct 167 ms 270320 KB Output is correct
11 Correct 165 ms 270036 KB Output is correct
12 Correct 167 ms 270040 KB Output is correct
13 Correct 168 ms 270352 KB Output is correct
14 Correct 159 ms 269920 KB Output is correct
15 Correct 920 ms 298992 KB Output is correct
16 Execution timed out 1064 ms 298872 KB Time limit exceeded
17 Halted 0 ms 0 KB -