oj.uz

Submission #160753

# Submission time Handle Problem Language Result Execution time Memory
160753 2019-10-29T19:17:12 Z davitmarg Sorting (IOI15_sorting) C++17
0 / 100
 3 ms 504 KB 
/*DavitMarg*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;
#ifndef death
	#include "sorting.h"
#endif

const int N = 200005;

int n,q,x[3*N],y[3*N];
vector<int> s,pos;

vector<pair<int,int>> solve(int r)
{
    vector<int> a=s,p=s;
    vector<pair<int,int>> ans;

    for(int i=0;i<r;i++)
        swap(a[x[i]],a[y[i]]);
    for(int i=0;i<n;i++)
		p[i]=pos[a[i]];
	a=s;

    for(int i=0;i<n;i++)
	{
		//cout<<p[i]<<" ,";
		if(i!=p[a[i]])
		{
            ans.PB(MP(p[a[i]],i));
            swap(a[p[a[i]]],a[i]);
		}
	}
	return ans;
}

int findSwapPairs(int N,int S[],int M,int X[],int Y[],int P[],int Q[])
{
	n=N;
	for(int i=0;i<n;i++)
		s.PB(S[i]);
	pos=s;
	for(int i=0;i<n;i++)
		pos[s[i]]=i;
	q=M;
	for(int i=0;i<q;i++)
	{
		x[i]=X[i];
		y[i]=Y[i];
	}
    int l=0,r=q,m,pos;
	while(l<=r)
	{
		m=(l+r)/2;
		vector<pair<int,int>> ans=solve(m);
        if(ans.size()<=m)
		{
			pos=m;
			r=m-1;
		}
		else
			l=m+1;
	}

	vector<pair<int,int>> ans=solve(pos);
	while(ans.size()<pos)
		ans.PB(MP(0,0));
	for(int j=0;j<ans.size();j++)
	{
		P[j]=ans[j].first;
		Q[j]=ans[j].second;
	}

	return pos;
}


#ifdef death

int main()
{
    int N,S[102],M,X[102],Y[102],P[102],Q[102],R;
    cin>>N;
    for(int i=0;i<N;i++)
		cin>>S[i];
	cin>>M;
    for(int i=0;i<M;i++)
		cin>>X[i]>>Y[i];
	R=findSwapPairs(N,S,M,X,Y,P,Q);
	cout<<R<<endl;
	for(int i=0;i<R;i++)
		cout<<P[i]<<" : "<<Q[i]<<endl;
    return 0;
}

#endif

/*

3
0 2 1
3
0 0
1 1
1 0




5
3 0 4 2 1
5
1 1
4 0
2 3
1 4
0 4

2 0
4 0
4 1
2 3
1 4
0 4

0 1 3 2 4

*/

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:60:70: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int findSwapPairs(int N,int S[],int M,int X[],int Y[],int P[],int Q[])
                                                                      ^
sorting.cpp:32:11: note: shadowed declaration is here
 const int N = 200005;
           ^
sorting.cpp:74:19: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
     int l=0,r=q,m,pos;
                   ^~~
sorting.cpp:35:15: note: shadowed declaration is here
 vector<int> s,pos;
               ^~~
sorting.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ans.size()<=m)
            ~~~~~~~~~~^~~
sorting.cpp:89:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ans.size()<pos)
        ~~~~~~~~~~^~~~
sorting.cpp:91:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<ans.size();j++)
              ~^~~~~~~~~~~
sorting.cpp:89:18: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  while(ans.size()<pos)
        ~~~~~~~~~~^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -