oj.uz

답안 #1053855

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1053855 2024-08-11T18:44:12 Z thatsgonzalez 정렬하기 (IOI15_sorting) C++14
36 / 100
 2 ms 1116 KB 
#include "sorting.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef vector<int> vi;
 
int n;
vector <int> s,x,y,p,q;
int ans = 0;
 
void merge(int l, int r, int mid){
	vi a;
	vi b;
	for(int i = l; i<=mid; i++) a.push_back(s[i]);
	for(int i = mid+1; i<=r; i++) b.push_back(s[i]);
	int i = 0, j = 0, k = l;
	while(i<=mid-l and j<=r-(mid+1)){
		if(a[i]>b[j]){ 
			if(k != j+mid+1){
				swap(s[x[ans]],s[y[ans]]);
				p[ans] = k; q[ans] = j+mid+1;
				ans++;
			}
			s[k] = b[j]; j++; k++; 
		}
		else{
			
			if(k != i+l){
				swap(s[x[ans]],s[y[ans]]);
				p[ans] = k; q[ans] = i+l;
				ans++;
			}
			s[k] = a[i]; i++; k++; 
		}
	}
 
	while(i<=mid-l){
		if(k != i+l){
			swap(s[x[ans]],s[y[ans]]);
			p[ans] = k; q[ans] = i+l;
			ans++;
		}
		s[k] = a[i]; i++; k++; 
	}
 
	while(j<=r-(mid+1)){
		if(k != j+mid+1){
			swap(s[x[ans]],s[y[ans]]);
			p[ans] = k; q[ans] = j+mid+1;
			ans++;
		}
		s[k] = b[j]; j++; k++; 
	}
 
 
 
}
 
void separate(int l, int r){
	if(l<r){
		int mid = (l+r)>>1;
		separate(l,mid);
		separate(mid+1,r);
		merge(l,r,mid);
	}
}
 
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	if(N == 1){
		P[0] = 0;
		Q[0] = 0;
		return 1;
	}
    n = N;
	for(int i = 0; i<n; i++) s.push_back(S[i]);
	for(int i = 0; i<M; i++) x.push_back(X[i]), y.push_back(Y[i]);
	p.assign(M,0);
	q.assign(M,0);
 
	int ind1 = 0, ind2 = 0; int mn = INT_MAX;
	for(int i = 0; i<N; i++){
		if(s[i]<mn){
			mn = s[i];
			ind1 = i;
		}
	}
	if(ind1 > 0){
		swap(s[x[ans]],s[y[ans]]);
		if(s[0]!=mn){
			p[ans] = 0; q[ans] = ind1;
			swap(s[0],s[ind1]);
		} 
		else p[ans] = 0, q[ans] = 0;
		ans++;
	}
	int indx = -1;
	if(x[ans]==y[ans]){
		indx = 1;
	}
	else indx = 0;
 
	mn = INT_MAX;
	for(int i = 1; i<n; i++){
		if(s[i]<mn){
			mn = s[i]; ind2 = i;
		} 
	}
	if(ind2>1){
		swap(s[x[ans]],s[y[ans]]);
		swap(s[indx],s[ind2]); p[ans] = min(indx,ind2); q[ans] = max(indx,ind2);ans++;
	}
	//separate(2,n-1);
 
	for(int i = 2; i<n; i++){
		for(int j = i+1; j<n; j++){
			if(s[i]>s[j]){
				swap(s[x[ans]],s[y[ans]]);
				if(s[i]>s[j]) swap(s[i],s[j]), p[ans] = i, q[ans] = j;
				else p[ans] = i, q[ans] = i; 
				ans++;
			}
		}
	}
	//for(auto &x: s) cout<<x<<" "; cout<<endl;
	if(s[0]>s[1]){
		swap(s[x[ans]],s[y[ans]]);
		p[ans] = 0, q[ans] = 0, ans++;
	}
	for(int i = 0; i<M; i++) P[i] = p[i], Q[i] = q[i];//, cout<<p[i]<<" "<<q[i]<<endl;
	return ans;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Incorrect 1 ms 860 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -