oj.uz

Submission #152284

# Submission time Handle Problem Language Result Execution time Memory
152284 2019-09-07T03:15:07 Z tinjyu Sorting (IOI15_sorting) C++14
100 / 100
 388 ms 34396 KB 
#include "sorting.h"
#include <iostream>
using namespace std;
long long int p[200005],b[200005],n,s[200005],m,x[2000005],y[2000005],a[2000005][2],t;
int check(int sum)
{
	//cout<<sum<<endl;
	for(int i=0;i<n;i++)
	{
		b[s[i]]=i;
		p[i]=s[i];
	}
	for(int i=0;i<sum;i++)
	{
		swap(b[p[x[i]]],b[p[y[i]]]);
		swap(p[x[i]],p[y[i]]);
		
	}
	
	int tmp=0;
	int tmp2[2000005][2],now=-1;
	for(int i=0;i<m;i++)
	{
		tmp2[i][0]=0;
		tmp2[i][1]=0;
	}
	
	for(int i=0;i<n;i++)
	{
		if(b[i]!=i)
		{
			now++;
			tmp++;
			int x1=i,y1=p[i];
			tmp2[now][0]=x1,tmp2[now][1]=y1;
			swap(p[b[i]],p[i]);
			swap(b[x1],b[y1]);
		}
		/*for(int j=0;j<n;j++)cout<<p[j]<<" ";
		cout<<endl;
		for(int j=0;j<n;j++)cout<<b[j]<<" ";
		cout<<endl;
		cout<<endl;*/
	}
	if(tmp<=sum){
		//cout<<endl;
		for(int i=0;i<sum;i++)
		{
			a[i][0]=tmp2[i][0];
			a[i][1]=tmp2[i][1];
		}
		return 1;
	}
	else return 0;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n=N,m=M;
    for(int i=0;i<n;i++)x[i]=X[i];
    for(int i=0;i<n;i++)y[i]=Y[i];
    for(int i=0;i<n;i++)s[i]=S[i];
    int l=0,r=n,ans;
    while(l<=r)
    {
    	int mid=(l+r)/2;
    	//cout<<l<<" "<<r<<" "<<mid<<endl;
    	if(check(mid)==1)
    	{
    		ans=mid;
    		r=mid-1;
		}
		else l=mid+1;
		//system("pause");
	}
	//cout<<ans<<endl;
	for(int i=0;i<n;i++)
	{
		b[s[i]]=i;
		p[i]=s[i];
	}
	for(int i=0;i<ans;i++)
	{
		swap(b[p[x[i]]],b[p[y[i]]]);
		swap(p[x[i]],p[y[i]]);
	
		P[i]=b[a[i][0]];
		Q[i]=b[a[i][1]];
		swap(b[p[P[i]]],b[p[Q[i]]]);
		swap(p[P[i]],p[Q[i]]);
	}
	return ans;
}

Compilation message

sorting.cpp: In function 'int check(int)':
sorting.cpp:34:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    int x1=i,y1=p[i];
                ~~~^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:61:15: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     int l=0,r=n,ans;
               ^
sorting.cpp:85:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   P[i]=b[a[i][0]];
        ~~~~~~~~~^
sorting.cpp:86:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   Q[i]=b[a[i][1]];
        ~~~~~~~~~^
sorting.cpp:61:17: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int l=0,r=n,ans;
                 ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 532 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 420 KB Output is correct
7 Correct 2 ms 380 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 532 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 420 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 412 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 3 ms 424 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 532 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 420 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 412 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 3 ms 424 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 3 ms 504 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 3 ms 760 KB Output is correct
22 Correct 3 ms 760 KB Output is correct
23 Correct 3 ms 760 KB Output is correct
24 Correct 3 ms 808 KB Output is correct
25 Correct 3 ms 760 KB Output is correct
26 Correct 3 ms 760 KB Output is correct
27 Correct 3 ms 760 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 680 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 744 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 4 ms 632 KB Output is correct
11 Correct 3 ms 636 KB Output is correct
12 Correct 3 ms 632 KB Output is correct
13 Correct 3 ms 704 KB Output is correct
14 Correct 3 ms 632 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 680 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 744 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 4 ms 632 KB Output is correct
11 Correct 3 ms 636 KB Output is correct
12 Correct 3 ms 632 KB Output is correct
13 Correct 3 ms 704 KB Output is correct
14 Correct 3 ms 632 KB Output is correct
15 Correct 221 ms 23516 KB Output is correct
16 Correct 278 ms 31196 KB Output is correct
17 Correct 349 ms 32888 KB Output is correct
18 Correct 85 ms 26488 KB Output is correct
19 Correct 177 ms 29944 KB Output is correct
20 Correct 203 ms 31756 KB Output is correct
21 Correct 203 ms 31736 KB Output is correct
22 Correct 218 ms 28280 KB Output is correct
23 Correct 270 ms 34152 KB Output is correct
24 Correct 361 ms 33500 KB Output is correct
25 Correct 350 ms 33196 KB Output is correct
26 Correct 257 ms 30932 KB Output is correct
27 Correct 243 ms 29944 KB Output is correct
28 Correct 348 ms 33108 KB Output is correct
29 Correct 321 ms 32288 KB Output is correct
30 Correct 219 ms 29300 KB Output is correct
31 Correct 388 ms 33272 KB Output is correct
32 Correct 267 ms 32852 KB Output is correct
33 Correct 340 ms 33528 KB Output is correct
34 Correct 277 ms 33448 KB Output is correct
35 Correct 172 ms 29688 KB Output is correct
36 Correct 80 ms 28408 KB Output is correct
37 Correct 280 ms 34396 KB Output is correct
38 Correct 262 ms 33036 KB Output is correct
39 Correct 273 ms 33280 KB Output is correct