oj.uz

Submission #1021278

# Submission time Handle Problem Language Result Execution time Memory
1021278 2024-07-12T16:37:16 Z huutuan Sorting (IOI15_sorting) C++14
36 / 100
 18 ms 4444 KB 
#include "sorting.h"

#include <bits/stdc++.h>

using namespace std;

struct DSU{
   int cnt;
   vector<int> lab;
   vector<pair<int*, int>> changes;
   void init(int n){
      cnt=0;
      lab.assign(n, -1);
   }
   int find_set(int u){
      return lab[u]<0?u:find_set(lab[u]);
   }
   void union_sets(int u, int v){
      u=find_set(u); v=find_set(v);
      if (u!=v){
         if (lab[u]>lab[v]) swap(u, v);
         changes.emplace_back(&lab[u], lab[u]);
         changes.emplace_back(&lab[v], lab[v]);
         lab[u]+=lab[v];
         lab[v]=u;
         changes.emplace_back(&cnt, cnt);
         ++cnt;
      }
   }
   void rollback(int size){
      while ((int)changes.size()>size){
         *changes.back().first=changes.back().second;
         changes.pop_back();
      }
   }
} dsu;

struct SegmentTree{
   int n;
   vector<vector<pair<int, int>>> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, {});
   }
   void update(int k, int l, int r, int L, int R, int u, int v){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         t[k].emplace_back(u, v);
         return;
      }
      int mid=(l+r)>>1;
      update(k<<1, l, mid, L, R, u, v);
      update(k<<1|1, mid+1, r, L, R, u, v);
   }
   int dfs(int k, int l, int r){
      int size=dsu.changes.size();
      for (auto &i:t[k]) dsu.union_sets(i.first, i.second);
      int ans=-1;
      if (l==r){
         if (dsu.cnt<=l) ans=l;
      }else{
         int mid=(l+r)>>1;
         if (ans==-1) ans=dfs(k<<1, l, mid);
         if (ans==-1) ans=dfs(k<<1|1, mid+1, r);
      }
      dsu.rollback(size);
      return ans;
   }
} st;

int a[200010], s[200010], pos[200010];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
   dsu.init(N);
   st.init(M+1);
   map<pair<int, int>, int> mp;
   for (int i=0; i<N; ++i) s[i]=S[i], a[i]=i, mp[{s[i], a[i]}]=0;
   for (int i=0; i<M; ++i){
      if (X[i]!=Y[i]){
         st.update(1, 0, M, mp[{s[X[i]], a[X[i]]}], i, s[X[i]], a[X[i]]);
         mp.erase({s[X[i]], a[X[i]]});
         st.update(1, 0, M, mp[{s[Y[i]], a[Y[i]]}], i, s[Y[i]], a[Y[i]]);
         mp.erase({s[Y[i]], a[Y[i]]});
         swap(a[X[i]], a[Y[i]]);
         mp[{s[X[i]], a[X[i]]}]=i+1;
         mp[{s[Y[i]], a[Y[i]]}]=i+1;
      }
   }
   for (auto &i:mp) st.update(1, 0, M-1, i.second, M, i.first.first, i.first.second);
   int ans=st.dfs(1, 0, M);
   if (ans==-1) return -1;
   for (int i=0; i<N; ++i) s[i]=S[i], a[i]=i, pos[s[i]]=i;
   for (int i=ans-1; i>=0; --i) swap(a[X[i]], a[Y[i]]);
   set<int> f;
   for (int i=0; i<N; ++i) if (a[i]!=s[i]) f.insert(i);
   for (int i=0; i<ans; ++i){
      P[i]=Q[i]=0;
      swap(a[X[i]], a[Y[i]]);
      swap(s[X[i]], s[Y[i]]);
      pos[s[X[i]]]=X[i];
      pos[s[Y[i]]]=Y[i];
      f.erase(X[i]); f.erase(Y[i]);
      if (a[X[i]]!=s[X[i]]) f.insert(X[i]);
      if (a[Y[i]]!=s[Y[i]]) f.insert(Y[i]);
      if (f.size()){
         int j=*f.begin(); f.erase(f.begin());
         int k=pos[a[j]];
         P[i]=j, Q[i]=k;
      }
      swap(s[P[i]], s[Q[i]]);
      pos[s[P[i]]]=P[i];
      pos[s[Q[i]]]=Q[i];
      f.erase(P[i]); f.erase(Q[i]);
      if (a[P[i]]!=s[P[i]]) f.insert(P[i]);
      if (a[Q[i]]!=s[Q[i]]) f.insert(Q[i]);
   }
   if (is_sorted(s, s+N)) return ans;
   return -1;
}

Compilation message

sorting.cpp: In member function 'int SegmentTree::dfs(int, int, int)':
sorting.cpp:56:32: warning: conversion from 'std::vector<std::pair<int*, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   56 |       int size=dsu.changes.size();
      |                ~~~~~~~~~~~~~~~~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 1 ms 708 KB Output is correct
12 Correct 1 ms 704 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 1 ms 708 KB Output is correct
12 Correct 1 ms 704 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 860 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 1 ms 860 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 17 ms 4444 KB Output is correct
22 Incorrect 18 ms 4428 KB Integer parameter [name=R] equals to -1, violates the range [0, 14340]
23 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 2136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 2136 KB Output isn't correct
2 Halted 0 ms 0 KB -