Submission #482501

#	Time	Username	Problem	Language	Result	Execution time	Memory
482501		mmonteiro	Sateliti (COCI20_satellti)	C++17	0 / 110	2 ms	332 KiB

Main

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define _ << " , " <<
#define bug(x) cout << #x << "  >>>>>>>  " << x << endl;
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
#define ii pair<int, int>
#define fi first
#define se second
#define UNTIL(t) while (clock() < (t) * CLOCKS_PER_SEC)
#define SZ(a) (int)a.size()
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int MAX = 2000000; //2 * 10^5
const int MOD = 1000000007; //10^9 + 7
const int OO = 0x3f3f3f3f; // 0x3f3f3f3f;
const double EPS = 1e-9;  //10^-9
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Info {
   int i, j, k, c;
   string r;
   Info(int _i, int _j, int _k, int _c, string _r) {
      i = _i; j = _j; k = _k; c = _c; r = _r;
   }
   Info(){}
};

string image[2005];
string s;
vector<int> sa, c;

// O(n)
void countSort()
{
	int n = sa.size();
	vector<int> buc(n), new_sa(n);
	for(int &w : sa)
		buc[c[w]]++;
	for(int i = 1; i < n; i++)	
		buc[i] += buc[i - 1];
	for(int i = n - 1; i >= 0; i--)
		new_sa[ --buc[ c[sa[i]] ] ] = sa[i];
	sa = new_sa;
}

// O(|s| * log|s|)
void buildSuffixArray()
{
	int n = s.size();
	sa.resize(n);
	c.resize(n);
	for(int i = 0; i < n; i++)
		sa[i] = i, c[i] = s[i];
	sort(sa.begin(), sa.end(), [&](int a, int b)
		{
			return c[a] < c[b];
		});
	c[sa[0]] = 0;
	for(int i = 1; i < n; i++)
		if(s[sa[i - 1]] == s[sa[i]])			
			c[sa[i]] = c[sa[i - 1]];
		else
			c[sa[i]] = c[sa[i - 1]] + 1;
	int k = 0;
	while((1 << k) < n)
	{
		for(int i = 0; i < n; i++)
			sa[i] = (sa[i] - (1 << k) + n) % n;
		countSort();
		vector<int> new_c(n);
		new_c[sa[0]] = 0;		
		for(int i = 1; i < n; i++)
		{
			pair<int, int> prev = {c[sa[i - 1]], c[(sa[i - 1] + (1 << k)) % n]};	
			pair<int, int> cur = {c[sa[i]], c[(sa[i] + (1 << k)) % n]};	
			if(prev == cur) new_c[sa[i]] = new_c[sa[i - 1]];
			else new_c[sa[i]] = new_c[sa[i - 1]] + 1;
		}	
		c = new_c;	
		k++;	
	}
}

pair<string, int> smallest_cyclic_shift(string a) {
   s = a;
   sa.clear();
   c.clear();
   buildSuffixArray();
   string ans;
   for(int i = sa[0]; i < SZ(s); i++)
      ans.push_back(s[i]);
   for(int i = 0; i < sa[0]; i++)
      ans.push_back(s[i]);
   return {ans, sa[0]};
}

void solve(){
   int n, m;

   cin >> n >> m;

   vector<int> mark(2 * n);

   for(int i = 0; i < n; i++) {
      cin >> image[i];
      int v = count(image[i].begin(), image[i].end(), '.');
      if(v == 0) mark[i] = 1;
      else if(v == m) mark[i] = -1;

   }
   for(int i = 0; i < n; i++)
      image[i + n] = image[i], mark[i + n] = mark[i];

   vector<Info> aux;

   for(int i = 0; i < n; i++) {
      if(mark[i] == -1) continue;
      int d = -1, k = -1, last = -1; // pos with dots
      for(int j = i; j < i + n; j++) {
         if(d == -1 and mark[j] == -1) d = j;
         if(k == -1 and mark[j] == 0) k = j;
         if(mark[j] == 1) last = j;
      }
      if(d == -1 or d > k) d = k;
      if(d == -1 or k == -1) d = k = last;

      if(k == -1) continue;

      auto [a, c] = smallest_cyclic_shift(image[ k ]);

      aux.push_back(Info(i, d, k, c, a));    
   }

   sort(aux.begin(), aux.end(), 
      [](Info a, Info b) {
         if(a.j - a.i != b.j - b.i) 
            return a.j - a.i > b.j - b.i;
         return a.r < b.r;
      }
   );

   if(aux.empty()) {
      for(int i = 0; i < n; i++)
         cout << image[i] << '\n';
      return;
   }

   // for(int i = 0; i < SZ(aux); i++)
   //    bug(aux[i].i _ aux[i].j _ aux[i].k _ aux[i].c _ aux[i].r);

   for(int i = 0; i < 2 * n; i++)
      image[i] += image[i];


   for(int i = aux[0].i; i < aux[0].i + n; i++) {
      for(int j = aux[0].c; j < aux[0].c + m; j++)
         cout << image[i][j];
      cout << '\n';
   }
}

int32_t main() {
   fastio;
   int t = 1;
   //cin >> t;
   for(int caso = 1; caso <= t; ++caso) {
      //cout << "Case #" << caso << ": ";
      solve();
   }
   return 0;
}
/*
Before submit:
   Check the corners cases
   Check solution restrictions

For implementation solutions:
   Check the flow of the variables

For intervals problems:
   Think about two pointers

For complete search:
   Think about cuts

If you get WA:
   Reread your code looking for stupid typos
   Try various manual testcases 
   Recheck the correctness of your algorithm
   Reread the statement
   Write a straightforward solution, create lots of testcases by yourself, and compare both solutions
   Generate random test cases and perform a stress test, comparing your solution with the one that you are sure is correct
   Change the coder (if you're with a team)
   Give up. You may have other tasks to solve.
*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 60