oj.uz

Submission #1021310

# Submission time Handle Problem Language Result Execution time Memory
1021310 2024-07-12T16:49:59 Z huutuan Sorting (IOI15_sorting) C++14
56 / 100
 1000 ms 128540 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], pa[200010];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
   M=min(M, N+100);
   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, pa[i]=i;
   for (int i=0; i<M; ++i){
      if (X[i]!=Y[i]){
         int p1=pa[X[i]], p2=pa[Y[i]];
         st.update(1, 0, M, mp[{s[p1], a[p1]}], i, s[p1], a[p1]);
         mp.erase({s[p1], a[p1]});
         st.update(1, 0, M, mp[{s[p2], a[p2]}], i, s[p2], a[p2]);
         mp.erase({s[p2], a[p2]});
         swap(a[p1], a[p2]);
         pa[a[p1]]=p1;
         pa[a[p2]]=p2;
         mp[{s[p1], a[p1]}]=i+1;
         mp[{s[p2], a[p2]}]=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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #3
16.0 / 16.0

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

Subtask #4
0 / 18.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1368 KB Output is correct
2 Correct 3 ms 1112 KB Output is correct
3 Correct 5 ms 1372 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 4 ms 1372 KB Output is correct
6 Correct 4 ms 1368 KB Output is correct
7 Correct 4 ms 1268 KB Output is correct
8 Correct 5 ms 1540 KB Output is correct
9 Correct 5 ms 1544 KB Output is correct
10 Correct 6 ms 1368 KB Output is correct
11 Correct 5 ms 1372 KB Output is correct
12 Correct 4 ms 1372 KB Output is correct
13 Correct 7 ms 1372 KB Output is correct
14 Correct 2 ms 860 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1368 KB Output is correct
2 Correct 3 ms 1112 KB Output is correct
3 Correct 5 ms 1372 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 4 ms 1372 KB Output is correct
6 Correct 4 ms 1368 KB Output is correct
7 Correct 4 ms 1268 KB Output is correct
8 Correct 5 ms 1540 KB Output is correct
9 Correct 5 ms 1544 KB Output is correct
10 Correct 6 ms 1368 KB Output is correct
11 Correct 5 ms 1372 KB Output is correct
12 Correct 4 ms 1372 KB Output is correct
13 Correct 7 ms 1372 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 438 ms 79896 KB Output is correct
16 Correct 815 ms 104752 KB Output is correct
17 Execution timed out 1053 ms 128540 KB Time limit exceeded
18 Halted 0 ms 0 KB -