제출 #138018

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
138018		arthurconmy	정렬하기 (IOI15_sorting)	C++14	0 / 100	6 ms	632 KiB

sorting

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

const int MAXN = 500;

int eend[MAXN];
int eend_inv[MAXN];
// int blank_slate[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[], int m, int X[], int Y[], int P[], int Q[])
{
  // for(int i=0; i<MAXN; i++) blank_slate[i]=i;

  for(int i=0; i<n; i++)
  {
    eend[i]=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++)
  {
    // for(int i=0; i<5; i++)
    // {
    //   cout << S[i] << " ";
    // }

    // cout << endl;

    // for(int i=0; i<5; i++)
    // {
    //   cout << eend_inv[i] << " ";
    // }

    //cout << endl;

    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;
      }

      one = S[pos_s];
      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;
      //return i+1;
    }

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

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

  return m;
}

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