제출 #288349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288349		shayan_p	Sorting (IOI15_sorting)	C++17	74 / 100	51 ms	21112 KiB

sorting

#include<bits/stdc++.h>
#include "sorting.h"

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;

const int maxn = 2e5 + 10, mod = 1e9 + 7;

bool mark[maxn];

int findSwapPairs(int q, int p[], int n, int a[], int b[], int A[], int B[]){
    fill(A, A + q, 0);
    fill(B, B + q, 0);
    auto need = [&](){
		    fill(mark, mark + n, 0);
		    int cnt = 0;
		    for(int i = 0; i < n; i++){
			int tmp = i;
			if(!mark[i]){
			    cnt++;
			    while(!mark[tmp]){
				mark[tmp] = 1;
				tmp = p[tmp];
			    }
			}
		    }
		    return n - cnt;
		};
    auto solve = [&](int q){
		     fill(mark, mark + n, 0);
		     vector<pii> tdo;
		     for(int i = 0; i < n; i++){
			 int tmp = i;
			 if(!mark[i]){
			     int SZ = sz(tdo);
			     while(!mark[tmp]){
				 if(i != tmp)
				     tdo.PB({i, tmp});
				 mark[tmp] = 1;
				 tmp = p[tmp];
			     }
			     reverse(tdo.begin() + SZ, tdo.end());
			 }
		     }
		     for(pii p : tdo)
			 cerr << p.F << " " << p.S << endl;
		     while(sz(tdo)){
			 q--;
			 int x = tdo.back().F, y = tdo.back().S;
			 tdo.pop_back();
			 for(int i = 0; i < n; i++)
			     if(p[i] == x){
				 A[q] = i;
				 break;
			     }
			 for(int i = 0; i < n; i++)
			     if(p[i] == y){
				 B[q] = i;
				 break;
			     }
			 swap(p[A[q]], p[B[q]]);
			 swap(p[a[q]], p[b[q]]);
		     }
		 };
    if(need() == 0)
	return 0;
    for(int i = 0; i < q; i++){
	swap(p[a[i]], p[b[i]]);
	if(need() <= i+1){
	    solve(i+1);
	    return i+1;
	}
    }
    assert(0);
}

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

sorting.cpp: In lambda function:
sorting.cpp:38:27: warning: declaration of 'int q' shadows a parameter [-Wshadow]
   38 |     auto solve = [&](int q){
      |                           ^
sorting.cpp:20:23: note: shadowed declaration is here
   20 | int findSwapPairs(int q, int p[], int n, int a[], int b[], int A[], int B[]){
      |                   ~~~~^
sorting.cpp:54:16: warning: declaration of 'p' shadows a lambda capture [-Wshadow]
   54 |        for(pii p : tdo)
      |                ^
sorting.cpp:49:12: note: shadowed declaration is here
   49 |      tmp = p[tmp];
      |            ^

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