oj.uz

답안 #640068

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
640068 2022-09-13T13:29:10 Z guilhermecpp Osmosmjerka (COCI17_osmosmjerka) C++17
100 / 160
 4000 ms 42520 KB 
#include <bits/stdc++.h>
using namespace std;

#define NMAX 510
#define NMAX2 2510
#define BASE 137
#define mod 1000000009

typedef long long int ll;

string mat[NMAX];

ll marc[NMAX][NMAX];
	
vector< string > seq;

ll dir_lin[] = {-1, -1, -1, 0, 0, 1, 1, 1};
ll dir_col[] = {-1, 0, 1, -1, 1, -1, 0, 1};

ll pot_base[NMAX2];

void BUILD_POT()
{

	ll i;

	pot_base[0] = 1;

	for(i = 1;i < NMAX2;i++)
	{
	
		pot_base[i] = (BASE * pot_base[i - 1]) % mod;
	
	}
	
	return;

}

ll MDC(ll a, ll b)
{

	if(b == 0)
	{
	
		return a;
	
	}
	
	return MDC(b, a % b);

}

int main()
{

	BUILD_POT();

	ll n, m, k, q, tam, lin, col, cur, pos, val, a, b, x, i, j;
	
	string aux;
	
	map< ll, ll > freq;
	
	cin >> n >> m >> k;
	
	k = min(k, n * m);
	
	for(i = 0;i < n;i++)
	{
	
		cin >> mat[i];
	
	}
	
	for(i = 0;i < n;i++)
	{
	
		for(j = 0;j < m;j++)
		{
		
			marc[i][j] = -1;
		
		}
	
	}
	
	for(cur = 0;cur < 8;cur++)
	{
	
		for(i = 0;i < n;i++)
		{
		
			for(j = 0;j < m;j++)
			{
			
				if(marc[i][j] != cur)
				{
				
					aux = "";
				
					lin = i;
					col = j;
				
					while(marc[lin][col] != cur)
					{
					
						marc[lin][col] = cur;
						
						aux.push_back(mat[lin][col]);
					
						lin = (lin + n + dir_lin[cur]) % n;
						col = (col + m + dir_col[cur]) % m;
					
					}
			
					seq.push_back(aux);
					
				}
			
			}
		
		}
		
	}
	
	q = (ll)(seq.size());
	
	a = 0;
	b = 0;
	
	for(i = 0;i < q;i++)
	{
	
		tam = (ll)(seq[i].size());
	
		val = (ll)(seq[i][0] - 'a' + 1);
	
		cur = val;
	
		for(j = 1;j < k;j++)
		{
	
			val = (ll)(seq[i][j % tam] - 'a' + 1);
		
			cur = (BASE * cur + val) % mod;
		
		}
		
		freq[cur]++;
		
		pos = k % tam;
		
		for(j = 1;j < tam;j++)
		{
	
			val = (ll)(seq[i][j - 1] - 'a' + 1);		
		
			cur = (cur + mod - (pot_base[k - 1] * val) % mod) % mod;
	
			val = (ll)(seq[i][pos] - 'a' + 1);
		
			cur = (BASE * cur + val) % mod;
			
			freq[cur]++;
			
			pos = (pos + 1) % tam;
			
		}
	
	}
	
	for(auto atual : freq)
	{
	
		a += atual.second * atual.second;
		b += atual.second;
	
	}
	
	b = b * b;
	
	x = MDC(a, b);
	
	a /= x;
	b /= x;
	
	cout << a << "/" << b << endl;

	return 0;

}

Subtask #1
100.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Incorrect 38 ms 4088 KB Output isn't correct
7 Incorrect 735 ms 25728 KB Output isn't correct
8 Execution timed out 4066 ms 42520 KB Time limit exceeded