제출 #1042745

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1042745		SonicML	정렬하기 (IOI15_sorting)	C++14	100 / 100	118 ms	26660 KiB

sorting

#include <iostream>
#include "sorting.h"
#include <vector> 

using namespace std;

int const NMAX = 5e5;

bool canSort(int n, int s[], int m, int x[], int y[]) {
  int aux[1 + NMAX], cycle = 0;
  int visit[1 + NMAX];
  for(int i = 0;i < n;i++) {
    aux[i] = s[i];
    visit[i] = false;
  }
  for(int i = 0;i < m;i++) {
    swap(aux[x[i]], aux[y[i]]);
  }
  for(int i = 0;i < n;i++) {
    int index = i;
    if(!visit[index]) {
      cycle++;
      while(!visit[index]) {
	visit[index] = true;
	index = aux[index];
      }
    }
  }
  return (m >= n - cycle);
}

int cautbinAns(int from, int to, int n, int s[], int x[], int y[]) {
  if(from >= to) {
    return from;
  } else {
    int mid = (from + to) / 2;
    if(canSort(n, s, mid, x, y)) {
      return cautbinAns(from, mid, n, s, x, y);
    } else {
      return cautbinAns(mid+1, to, n, s, x, y);
    }
  }
}
       
int arr[1 + NMAX];
int arrPos[1 + NMAX];

vector <pair <int, int>> swaps;

void buildSwap(int n, int s[], int m, int x[], int y[]) {
  int aux[1 + NMAX];
  int visit[1 + NMAX];
  for(int i = 0;i < n;i++) {
    aux[i] = s[i];
    visit[i] = false;
  }
  for(int i = 0;i < m;i++) {
    swap(aux[x[i]], aux[y[i]]);
  }

  for(int i = 0;i < n;i++) {
    //cerr << aux[i] << ' ';
    int index = i, to;
    if(!visit[index]) {
      while(!visit[index]) {
	visit[index] = true;
        to = aux[index];	
	if(!visit[to]) {
          swaps.push_back({index, to});
	}
	//cerr << index << ' ' << aux[index] << '\n';
	index = to;
      }
    }
  }
  //cerr << '\n';
}

void buildArr(int n, int s[]) {
  for(int i = 0;i < n;i++) {
    arr[i] = s[i];
    arrPos[arr[i]] = i;
  }
}

void printArr(int n) {
  for(int i = 0;i < n;i++) {
    cerr << arr[i] << ' ';
  }
  cerr << "\n";
}

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
  int ans = cautbinAns(0, m, n, s, x, y), fix = 0;
  buildSwap(n, s, ans, x, y); 
  buildArr(n, s);
  int ind = 0;
  for(int i = 0;i < ans;i++) {
    int a = x[i], b = y[i];
    swap(arrPos[arr[a]], arrPos[arr[b]]);
    swap(arr[a], arr[b]);
    if(ind < swaps.size()) {
      p[i] = arrPos[swaps[ind].first];
      q[i] = arrPos[swaps[ind].second];
      //cerr << swaps[ind].first << ' ' << swaps[ind].second << " : " << p[i] << ' ' << q[i] << "\n";
      swap(arrPos[arr[p[i]]], arrPos[arr[q[i]]]);
      swap(arr[p[i]], arr[q[i]]);
      ind++;
    } else {
      p[i] = q[i] = 0;
    }
    //printArr(n);
  }
  return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:102:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     if(ind < swaps.size()) {
      |        ~~~~^~~~~~~~~~~~~~
sorting.cpp:94:43: warning: unused variable 'fix' [-Wunused-variable]
   94 |   int ans = cautbinAns(0, m, n, s, x, y), fix = 0;
      |                                           ^~~

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