우 객 망 여름 ACM 다 교 훈련소 (제4 회) J: Hash Function (데이터 구조 + 난동)

제목 의 대의:
a [i]% n 이 충돌 할 때 충돌 이 없 는 곳 으로 뒤로 미 루 는 hash 방식 이 있 습 니 다.현재 hash 뒤의 순 서 를 드 립 니 다. hash 전의 순 서 를 내 놓 을 수 있 습 니까? 가능 하 다 면 최소 사전 순 서 를 출력 할 수 있 습 니 다.
 
문제 풀이 방향:
처음에 경 기 를 시작 할 때 토폴로지 순 서 를 생각 했 는데 토폴로지 순 서 는 A 사건 이 발생 하기 전에 B 사건 이 발생 할 수 없 기 때문이다.그러면 만약 에 내 가 a [i]% n 의 결과 가 pos 라면 pos 에서 i 까지 의 모든 수 에 대해 a [i] 에 대해 한 줄 한 줄 방향 이 있다 는 것 은 이 수가 선택 되 기 전에 a [i] 이 수 는 선택 할 수 없다 는 것 을 나타 낸다. 사실은 토폴로지 정렬 의 정의 에 완벽 하 게 부합 되 지만 극한 상황 에서 의 변 수 는 n ^ 2 개 이 고 이 문제 n = 2e6 이기 때문에 최적화 해 야 한다.사실 그때 경기 할 때 도 생각 했 어 요.  바로 A - > B B - > C 에 대해 A - > C 라 는 쪽 을 연결 할 필요 가 없다 는 것 이다.하지만 이 쪽 을 어떻게 최적화 해 야 할 지 모 르 고 게이 가 되 었 다.경기 가 끝 난 후에 많은 팀 들 이 사실 매우 교묘 한 방법 으로 아무렇게나 지나 간 것 을 발견 하 였 다.
여기 서 한 가지 방법 을 말 하 는데, 극악무도 한 csdn 은 반 쯤 쓰 고 무 너 졌 는데, 결 과 는 초고 가 없어 서 쓰 고 싶 지 않 게 되 었 다.
먼저 모든 정확 한 위치의 수 를 우선 대기 열 에 추가 합 니 다. 우리 가 대기 열 에서 하나의 수 를 꺼 냈 을 때 각각 두 개의 변수 l = (pos - 1)% n, r = (pos + 1)% n 을 기록 한 다음 에 l r 두 위치의 수 를 이전에 꺼 냈 는 지 여 부 를 판단 합 니 다. 만약 그렇다면 답 이 되 지 않 은 l 과 r 를 찾 을 때 까지 계속 왼쪽으로 이동 합 니 다.이후 의 조작 은 a [r]% n 이 위치의 수가 이미 답안 으로 추출 되 었 는 지 직접 판단 합 니 다. 만약 그렇다면 a [r] 를 우선 대기 열 에 넣 으 면 됩 니 다.
 
Ac 코드:

#include 
using namespace std;
const int maxn=2e6+5;
int n,tot,a[maxn],nex[maxn],pre[maxn];
vector ans;
bool in[maxn],vis[maxn];
void init()
{
    ans.clear();tot=0;
    for(int i=0;i<=n;i++) vis[i]=0;
    for(int i=0;i<=n;i++) in[i]=0;
    for(int i=0;i<=n;i++) nex[i]=pre[i]=0;
}
int main()
{
    int QAQ;
    scanf("%d",&QAQ);
    while(QAQ--)
    {
        scanf("%d",&n);
        init();
        priority_queue< pair,vector>,greater> > que;
        for(int i=0;i=((n+r-a[r]%n)%n)) //  a[r]               
            {
                que.push({a[r],r});
                in[r]=1;
            }
        }
        if(tot!=ans.size()) printf("-1
");
        else if(tot==0) printf("
");
        else
        {
            for(int i=0;i