Submission #781667

#	Time	Username	Problem	Language	Result	Execution time	Memory
781667		vjudge1	Sorting (IOI15_sorting)	C++17	74 / 100	1096 ms	449168 KiB

sorting

#include<bits/stdc++.h>
using namespace std;

#include "sorting.h"

int c(vector<int> s){
    int ans=0;
    vector<int> pos(s.size());

    for(int i=0; i<pos.size(); i++) pos[s[i]]=i;

    for(int i=0; i<pos.size(); i++){
        if(s[i]!=i){
            ans++;
            swap(s[i], s[pos[i]]);
            swap(pos[s[i]], pos[s[pos[i]]]);
        }
    }
    return ans;
}

int findSwapPairs(int n, int S[], int m, int x[], int y[], int p[], int q[]) {
    vector<int> s(n);    
    vector<vector<int>> a;

    for(int i = 0; i < n; i++) s[i] = S[i];

    for(int i=0; i<n; i++){
        vector<int> pos(n);

        for(int i=0; i<n; i++) pos[s[i]]=i;
       
        if(c(s)<=i){
            int j=0;
            for(int l=i-1; l>=0; l--){
                while(j<n&&s[j]==j) j++;
                if(j<n&&s[j]!=j){
                    q[l]=a[l][s[pos[j]]]; p[l]=a[l][s[j]];
                    swap(s[pos[j]], s[j]);
                    //int f=pos[j], g=j;

                    swap(pos[s[pos[j]]], pos[s[j]]);
                    
                    
                    j++;
                }
            }

      //      for(auto i: s) cout<<i<<" ";

            return i;
        }
  

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

        a.push_back(pos);

    }
    return 0;
}
void f(){
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
}



/*
int main()
{
	f();
	int N, M;
	cin >> N;
	int *S = (int*)malloc(sizeof(int) * (unsigned int)N);
	for (int i = 0; i < N; ++i)
		cin >> S[i];

	cin >> M;
	int *X = (int*)malloc(sizeof(int) * (unsigned int)M), *Y = (int*)malloc(sizeof(int) * (unsigned int)M);
	for (int i = 0; i < M; ++i) {
	    cin >> X[i] >> Y[i];
	}
	int *P = (int*)malloc(sizeof(int) * (unsigned int)M), *Q = (int*)malloc(sizeof(int) * (unsigned int)M);
	
    int ans = findSwapPairs(N, S, M, X, Y, P, Q);
    cout<<ans<<"\n";    
	for (int i = 0; i < ans; ++i)
	   cout<<P[i]<<" "<<Q[i]<<"\n";
	return 0;
}
*/

Compilation message (stderr)

sorting.cpp: In function 'int c(std::vector<int>)':
sorting.cpp:10:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int i=0; i<pos.size(); i++) pos[s[i]]=i;
      |                  ~^~~~~~~~~~~
sorting.cpp:12:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0; i<pos.size(); i++){
      |                  ~^~~~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:31:17: warning: declaration of 'i' shadows a previous local [-Wshadow]
   31 |         for(int i=0; i<n; i++) pos[s[i]]=i;
      |                 ^
sorting.cpp:28:13: note: shadowed declaration is here
   28 |     for(int i=0; i<n; i++){
      |             ^
sorting.cpp:56:17: warning: declaration of 'i' shadows a previous local [-Wshadow]
   56 |         for(int i=0; i<n; i++) pos[s[i]]=i;
      |                 ^
sorting.cpp:28:13: note: shadowed declaration is here
   28 |     for(int i=0; i<n; i++){
      |             ^
sorting.cpp:22:39: warning: unused parameter 'm' [-Wunused-parameter]
   22 | int findSwapPairs(int n, int S[], int m, int x[], int y[], int p[], int q[]) {
      |                                   ~~~~^
sorting.cpp: In function 'void f()':
sorting.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen("in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sorting.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen("out.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 0 / 26