답안 #718534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
718534	2023-04-04T09:41:26 Z	myrcella	정렬하기 (IOI15_sorting)	C++17	74 / 100	1000 ms	442312 KB

sorting

//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];	
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:40:29: warning: unused parameter 'val' [-Wunused-parameter]
   40 | void update(int x,int y,int val) {
      |                         ~~~~^~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:100:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |   int mid=l+r>>1;
      |           ~^~

Subtask #1

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	227 ms	404216 KB	Output is correct
2	Correct	227 ms	404256 KB	Output is correct
3	Correct	231 ms	404312 KB	Output is correct
4	Correct	234 ms	404236 KB	Output is correct
5	Correct	226 ms	404244 KB	Output is correct
6	Correct	228 ms	404312 KB	Output is correct
7	Correct	227 ms	404276 KB	Output is correct

Subtask #2

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	227 ms	404216 KB	Output is correct
2	Correct	227 ms	404256 KB	Output is correct
3	Correct	231 ms	404312 KB	Output is correct
4	Correct	234 ms	404236 KB	Output is correct
5	Correct	226 ms	404244 KB	Output is correct
6	Correct	228 ms	404312 KB	Output is correct
7	Correct	227 ms	404276 KB	Output is correct
8	Correct	230 ms	404148 KB	Output is correct
9	Correct	227 ms	404264 KB	Output is correct
10	Correct	231 ms	404388 KB	Output is correct
11	Correct	234 ms	404344 KB	Output is correct
12	Correct	226 ms	404356 KB	Output is correct

Subtask #3

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	236 ms	404256 KB	Output is correct
2	Correct	231 ms	404268 KB	Output is correct
3	Correct	232 ms	404300 KB	Output is correct
4	Correct	226 ms	404344 KB	Output is correct
5	Correct	230 ms	404300 KB	Output is correct
6	Correct	228 ms	404260 KB	Output is correct

Subtask #4

18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	227 ms	404216 KB	Output is correct
2	Correct	227 ms	404256 KB	Output is correct
3	Correct	231 ms	404312 KB	Output is correct
4	Correct	234 ms	404236 KB	Output is correct
5	Correct	226 ms	404244 KB	Output is correct
6	Correct	228 ms	404312 KB	Output is correct
7	Correct	227 ms	404276 KB	Output is correct
8	Correct	230 ms	404148 KB	Output is correct
9	Correct	227 ms	404264 KB	Output is correct
10	Correct	231 ms	404388 KB	Output is correct
11	Correct	234 ms	404344 KB	Output is correct
12	Correct	226 ms	404356 KB	Output is correct
13	Correct	236 ms	404256 KB	Output is correct
14	Correct	231 ms	404268 KB	Output is correct
15	Correct	232 ms	404300 KB	Output is correct
16	Correct	226 ms	404344 KB	Output is correct
17	Correct	230 ms	404300 KB	Output is correct
18	Correct	228 ms	404260 KB	Output is correct
19	Correct	231 ms	404160 KB	Output is correct
20	Correct	225 ms	404244 KB	Output is correct
21	Correct	238 ms	404684 KB	Output is correct
22	Correct	233 ms	404652 KB	Output is correct
23	Correct	230 ms	404776 KB	Output is correct
24	Correct	231 ms	404708 KB	Output is correct
25	Correct	236 ms	404592 KB	Output is correct
26	Correct	231 ms	404700 KB	Output is correct
27	Correct	231 ms	404756 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	238 ms	404724 KB	Output is correct
2	Correct	242 ms	404600 KB	Output is correct
3	Correct	235 ms	404680 KB	Output is correct
4	Correct	232 ms	404816 KB	Output is correct
5	Correct	238 ms	404892 KB	Output is correct
6	Correct	229 ms	404732 KB	Output is correct
7	Correct	234 ms	404924 KB	Output is correct
8	Correct	236 ms	405136 KB	Output is correct
9	Correct	236 ms	404964 KB	Output is correct
10	Correct	236 ms	404876 KB	Output is correct
11	Correct	239 ms	404820 KB	Output is correct
12	Correct	246 ms	404752 KB	Output is correct
13	Correct	233 ms	404908 KB	Output is correct
14	Correct	237 ms	404392 KB	Output is correct

Subtask #6

0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	238 ms	404724 KB	Output is correct
2	Correct	242 ms	404600 KB	Output is correct
3	Correct	235 ms	404680 KB	Output is correct
4	Correct	232 ms	404816 KB	Output is correct
5	Correct	238 ms	404892 KB	Output is correct
6	Correct	229 ms	404732 KB	Output is correct
7	Correct	234 ms	404924 KB	Output is correct
8	Correct	236 ms	405136 KB	Output is correct
9	Correct	236 ms	404964 KB	Output is correct
10	Correct	236 ms	404876 KB	Output is correct
11	Correct	239 ms	404820 KB	Output is correct
12	Correct	246 ms	404752 KB	Output is correct
13	Correct	233 ms	404908 KB	Output is correct
14	Correct	237 ms	404392 KB	Output is correct
15	Correct	979 ms	434604 KB	Output is correct
16	Execution timed out	1061 ms	442312 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-