oj.uz

Submission #138011

# Submission time Handle Problem Language Result Execution time Memory
138011 2019-07-28T22:21:01 Z arthurconmy Sorting (IOI15_sorting) C++14
0 / 100
 6 ms 632 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500;

int eend[MAXN];
int eend_inv[MAXN];

void eend_swap(int a, int b)
{
  int one = eend[a];
  int two = eend[b];

  eend[a]=two;
  eend[b]=one;
}

void eend_inv_swap(int a, int b)
{
  int one = eend_inv[a];
  int two = eend_inv[b];

  eend_inv[a]=two;
  eend_inv[b]=one;
}

int findSwapPairs(int n, int S[MAXN], int m, int X[MAXN], int Y[MAXN], int P[MAXN], int Q[MAXN])
{

  for(int i=0; i<n; i++)
  {
    eend[i]=S[i];
  }

  for(int i=0; i<m; i++)
  {
    eend_swap(X[i],Y[i]);
  }

  for(int i=0; i<n; i++)
  {
    eend_inv[eend[i]]=i;
  }

  // for(int i=0; i<n; i++)
  // {
  //   cout << i << " " << eend[i] << endl;
  // }

  int cur_sort=0;

  for(int i=0; i<m; i++)
  {
    eend_inv_swap(X[i],Y[i]); // correct ???

    int one = S[X[i]];
    int two = S[Y[i]];

    S[X[i]]=two;
    S[Y[i]]=one;

    bool upd=0;

    while(cur_sort < n)
    {
      int pos_s=-1;
      int pos_e=-1;

      for(int j=0; j<n; j++)
      {
        if(S[j]==cur_sort) pos_s=j;
        if(eend_inv[j]==cur_sort) pos_e=j;
      }

      if(pos_e == pos_s && pos_e != -1)
      {
        // cout << cur_sort << " is sorted bro" << endl;

        cur_sort++;
        continue;
      }

      int one = S[pos_s];
      int two = S[pos_e];

      S[pos_s]=two;
      S[pos_e]=one;

      P[i]=pos_s;
      Q[i]=pos_e;
      upd=1;

      cur_sort++;
      break;
    }  
    
    if(!upd)
    {
      P[i]=0;
      Q[i]=0;
    }

    //cout << P[i] << " " << Q[i] << endl;
  }

  //cout << "done" << endl;

  return m;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:83:11: warning: declaration of 'one' shadows a previous local [-Wshadow]
       int one = S[pos_s];
           ^~~
sorting.cpp:56:9: note: shadowed declaration is here
     int one = S[X[i]];
         ^~~
sorting.cpp:84:11: warning: declaration of 'two' shadows a previous local [-Wshadow]
       int two = S[pos_e];
           ^~~
sorting.cpp:57:9: note: shadowed declaration is here
     int two = S[Y[i]];
         ^~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -