Submission #1076373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076373		bleahbleah	Brought Down the Grading Server? (CEOI23_balance)	C++17	100 / 100	313 ms	42940 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], deg[nmax];
   
   void add_edge(int *a, int *b) {
      if(*a == *b) return;
      deg[*a]++;
      deg[*b]++;
      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(int bit = 1; bit >= 0; bit--) {
         for(auto x : V) {
            st.emplace_back(x);
            while(!st.empty()) {
               int node = st.back();
               st.pop_back();
               if(deg[node] % 2 < bit) { st.clear(); break; }
               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);
               
               //cerr << *edgeref[u].first << " --> " << *edgeref[u].second << '\n';
               
               deg[*edgeref[u].second]--;
               deg[node]--;
               
               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);
   map<int,pii> cnt;
   for(int i = 0; i < 2; i++){
      for(int l = 0; l < n; l++) {
         if(i == 0) cnt[mat[l][i]].first++;
         if(i == 1) cnt[mat[l][i]].second++;
      }
   }
   
   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: 10 / 10
• Subtask 2-1: 15 / 15
• Subtask 2-2: 5 / 5
• Subtask 2-3: 5 / 5
• Subtask 3-1: 15 / 15
• Subtask 3-2: 5 / 5
• Subtask 3-3: 5 / 5
• Subtask 4-1: 20 / 20
• Subtask 4-2: 10 / 10
• Subtask 4-3: 10 / 10