Submission #999618

#	Time	Username	Problem	Language	Result	Execution time	Memory
999618		Gilgamesh	정렬하기 (IOI15_sorting)	C++17	100 / 100	192 ms	36576 KiB

sorting

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <unordered_map>

using namespace std;

const int MAXN = 1000010;

typedef pair<int, int> ii;
typedef long long ll;

int n, m;
vector<int> ar;

int ar1[MAXN], ar2[MAXN];

vector<ii> ans;

bool check(int t) {
	vector<int> cur = ar;
	for (int i = 0; i < t; i++) {
		swap(cur[ar1[i]], cur[ar2[i]]);
	}
	vector<ii> swaps;
	for (int i = 0; i < n; i++) {
		while (cur[i] != i) {
			swaps.emplace_back(cur[i], cur[cur[i]]);
			swap(cur[i], cur[cur[i]]);
		}
	}
	while (swaps.size() < t) swaps.emplace_back(0, 0);
	if (swaps.size() > t) return false;
	cur = ar;
	vector<int> ind(n);
	for (int i = 0; i < n; i++) {
		ind[cur[i]] = i;
	}
	vector<ii> ret;
	for (int i = 0; i < t; i++) {
		int x = ar1[i];
		int y = ar2[i];
		swap(ind[cur[x]], ind[cur[y]]);
		swap(cur[x], cur[y]);

		x = swaps[i].first;
		y = swaps[i].second;
		ret.emplace_back(ind[x], ind[y]);
		swap(cur[ind[x]], cur[ind[y]]);
		swap(ind[x], ind[y]);
	}
	ans = ret;
	return true;
}

void setIO(string s) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

int findSwapPairs(int N, int* s, int M, int* x, int* y, int* p, int* q) {
	n = N;
	ar = vector<int>(n);
	for (int i = 0; i < n; i++) {
		ar[i] = s[i];
	}
    m = M;
	int sw = 0;
	for (int i = 0; i < m; i++) {
		ar1[i] = x[i];
        ar2[i] = y[i];
	}
	int lo = 0, hi = m;
	while (lo < hi) {
		int mid = lo + (hi - lo) / 2;
		if (check(mid)) {
			hi = mid;
		}
		else lo = mid + 1;
	}
	check(lo);
	for (int i = 0; i < ans.size(); i++) {
        p[i] = ans[i].first;
        q[i] = ans[i].second;
	}
    return ans.size();
}

Compilation message (stderr)

sorting.cpp: In function 'bool check(int)':
sorting.cpp:47:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |  while (swaps.size() < t) swaps.emplace_back(0, 0);
      |         ~~~~~~~~~~~~~^~~
sorting.cpp:48:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |  if (swaps.size() > t) return false;
      |      ~~~~~~~~~~~~~^~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |  for (int i = 0; i < ans.size(); i++) {
      |                  ~~^~~~~~~~~~~~
sorting.cpp:103:20: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  103 |     return ans.size();
      |            ~~~~~~~~^~
sorting.cpp:85:6: warning: unused variable 'sw' [-Wunused-variable]
   85 |  int sw = 0;
      |      ^~
sorting.cpp: In function 'void setIO(std::string)':
sorting.cpp:74:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sorting.cpp:75:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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