Submission #1076353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076353		bleahbleah	Brought Down the Grading Server? (CEOI23_balance)	C++17	50 / 100	232 ms	33924 KiB

balance

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 5e5 + 5;

namespace Equalise {
   vector<pair<int*, int*>> edgeref;
   vector<int> g[nmax];
   int pointer[nmax], occ[nmax];
   
   void add_edge(int *a, int *b) {
      if(*a == *b) return;
      g[*a].emplace_back(sz(edgeref));
      g[*b].emplace_back(sz(edgeref));
      edgeref.emplace_back(a, b);
   }
   void init(vector<int> V) {
      vector<int> st;
      for(auto x : V) {
         st.emplace_back(x);
         while(!st.empty()) {
            int node = st.back();
            st.pop_back();
            if(pointer[node] == sz(g[node])) continue;
            st.emplace_back(node);
            int u = g[node][pointer[node]++];
            if(occ[u] == 1) continue;
            
            occ[u] = 1;
            if(*edgeref[u].first != node) swap(*edgeref[u].first, *edgeref[u].second);
            st.emplace_back(*edgeref[u].second);
         }
      }
      
      for(auto x : V) pointer[x] = 0, g[x].clear();
      for(int i = 0; i < sz(edgeref); i++) occ[i] = 0;
      edgeref.clear();
   }
}

vector<vector<int>> mat;

void divide(int l, int r) {
   if(l == r) return;
   int mid = (l + r) >> 1;
   vector<int> a;
   for(int t = mid, t1 = mid + 1; t >= l; t--, t1++) {
      for(int i = 0; i < sz(mat); i++)
         Equalise::add_edge(&mat[i][t], &mat[i][t1]), a.emplace_back(mat[i][t]), a.emplace_back(mat[i][t1]);
   }
   Equalise::init(a);
   
   divide(l, mid);
   divide(mid + 1, r);
   
}

signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int n, s, t;
   cin >> n >> s >> t; 
   mat.resize(n, vector<int>(s));
   for(auto &v : mat) for(auto &x : v) cin >> x;
   divide(0, s - 1);
   
   for(auto &v : mat) { for(auto &x : v) cout << x << ' '; cout << '\n'; }
   return 0;
}

/**
      Töte es durch genaue Untersuchung\Töte es kann es nur noch schlimmer machen\Es lässt es irgendwie atmen
--
*/ 

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2-1: 15 / 15
• Subtask 2-2: 0 / 5
• Subtask 2-3: 0 / 5
• Subtask 3-1: 15 / 15
• Subtask 3-2: 0 / 5
• Subtask 3-3: 0 / 5
• Subtask 4-1: 20 / 20
• Subtask 4-2: 0 / 10
• Subtask 4-3: 0 / 10