Skip to content

Instantly share code, notes, and snippets.

@e673
Last active December 12, 2020 12:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save e673/5e79ec81f94bb2dca9c405e5e9f6bd08 to your computer and use it in GitHub Desktop.
Save e673/5e79ec81f94bb2dca9c405e5e9f6bd08 to your computer and use it in GitHub Desktop.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApp1
{
using static Console;
class Program
{
class Item
{
public bool Start;
public int V;
public int Pos;
public Item Next;
public Item Prev;
}
static (int pos, int len) Process(Item[] P, bool reversed)
{
int N = P.Length;
for (int i = 0; i < N; i++)
{
P[i].Next = P[(i + 1) % N];
P[i].Prev = P[(i + N - 1) % N];
}
var cur = P[0];
int M = N;
for (int i = 0; i < N; i++)
{
if (cur.Start && !cur.Next.Start && cur.V == cur.Next.V)
{
var prev = cur.Prev;
var next = cur.Next.Next;
prev.Next = next;
next.Prev = prev;
cur = prev;
M -= 2;
if (M == 0)
{
WriteLine("1 {0}", N / 2);
return (1, N);
}
}
else
{
cur = cur.Next;
}
}
var max = 0;
var pos = 0;
for (int i = 0; i < N; i++)
{
var next = reversed ? cur.Prev : cur.Next;
var d = (next.Pos - cur.Pos + N - 1) % N;
if (d > max)
{
max = d;
pos = reversed ? (cur.Pos + 1) % N: cur.Pos;
}
cur = next;
}
return (pos + 1, max / 2);
}
static void Main(string[] args)
{
var s1 = ReadLine();
var s2 = ReadLine();
int N = int.Parse(s1);
var P = s2.Split(' ').Select((x, i) => new Item { Start = x[0] == 's', V = int.Parse(x.Substring(1)), Pos = i }).ToArray();
var v1 = Process(P, false);
var v2 = Process(P.Reverse().ToArray(), true);
if (v1.len < v2.len)
v1 = v2;
WriteLine("{0} {1}", v1.pos, v1.len);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment