이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pp;
int n,m;
int state=0;
int pos[200010];
int s[200010];
int sw[600010][2];
bool ch[200010];
int ans;
vector<pp> pq;
void swaps(int p1,int p2)
{
int temp=s[p1];
s[p1]=s[p2];
s[p2]=temp;
}
void change_to_state(int st)
{
while(state<st)
{
state++;
swaps(sw[state][0],sw[state][1]);
}
while(state>st)
{
swaps(sw[state][0],sw[state][1]);
state--;
}
}
int count_cycle()
{
for(int i=0;i<n;i++) ch[i]=false;
int cycle_num=0,cur;
for(int i=0;i<n;i++)
{
if(ch[i]) continue;
cycle_num++;
ch[i]=true;
cur=s[i];
while(cur!=i)
{
ch[cur]=true;
cur=s[cur];
}
}
return cycle_num;
}
void find_ans()
{
int hi=m,low=0,av;
while(hi>low)
{
av=(hi+low)>>1;
change_to_state(av);
if(count_cycle()+av>=n) hi=av;
else low=av+1;
}
ans=hi;
return;
}
void get_pq()
{
change_to_state(ans);
for(int i=0;i<n;i++)
{
while(s[i]!=i)
{
pq.push_back({i,s[i]});
swaps(i,s[i]);
}
}
while(pq.size()<ans)
{
pq.push_back({1,1});
}
}
void change_pq()
{
for(int i=0;i<n;i++) pos[i]=i;
int temp;
for(int i=ans-2;i>=0;i--)
{
swaps(pos[sw[i+2][0]],pos[sw[i+2][1]]);
temp=pos[sw[i+2][0]];
pos[sw[i+2][0]]=pos[sw[i+2][1]];
pos[sw[i+2][1]]=temp;
pq[i]={s[pq[i].first],s[pq[i].second]};
}
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n=N;
m=M;
for(int i=0;i<n;i++)
{
s[i]=S[i];
}
for(int i=0;i<m;i++)
{
sw[i+1][0]=X[i];
sw[i+1][1]=Y[i];
}
find_ans();
get_pq();
change_pq();
for(int i=0;i<ans;i++)
{
P[i]=pq[i].first;
Q[i]=pq[i].second;
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
sorting.cpp: In function 'void get_pq()':
sorting.cpp:80:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
80 | while(pq.size()<ans)
| ~~~~~~~~~^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |