7738 | 2024. 01. 10 20:03:43 | ananász | Találkozás | csharp | Időlimit túllépés 20/55 | 300ms | 36472 KiB |
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace talalkozas
{
class Program
{
static void Main(string[] args)
{
long N = int.Parse(Console.ReadLine());
long fele = N / 2;
long utolsotav = 0;
if (N % 2 == 1)
{
fele++;
}
long[] tavozott = new long[100000];
long[] erkezett = new long[100000];
for (int i = 0; i < N; i++)
{
string[] st = Console.ReadLine().Split();
long erk = int.Parse(st[0]) - 1;
long tav = int.Parse(st[1]);
if (tav < 99999)
{
tavozott[tav]--;
utolsotav = tav;
}
erkezett[erk]++;
}
long[] idopontok = new long[100000];
idopontok[0] = erkezett[0] + tavozott[0];
for (int i = 1; i < 100000; i++)
{
idopontok[i] = idopontok[i-1]+ erkezett[i] + tavozott[i];
}
//1. távozáskor mennyien voltak?
long id = 0;
while (tavozott[id] == 0 && idopontok[id] < fele)
{
id++;
}
if (idopontok[id] >= fele)//ha egy időpontban elérték
{
Console.WriteLine(1);
Console.WriteLine(id + 1);
}
else //itt az id az első távozás ideje
{
long hossz = 1;
long akt = idopontok[id - 1];
long elozotav = id+1;//az első távozás utáni index
while (akt < fele)
{
hossz++;
akt += erkezett[id];
id++;
}
id--;
long minid = id;
long min = hossz;
while (elozotav < utolsotav)
{
id = elozotav;
while (tavozott[id] == 0 && idopontok[id] < fele)
{
id++;
}
if (idopontok[id] >= fele)
{
Console.WriteLine(1);
Console.WriteLine(id + 1);
break;
}
elozotav = id+1;
hossz = 1;
akt = idopontok[id - 1];
while (id<100000&&akt < fele&&hossz<=min)
{
akt += erkezett[id];
hossz++;
id++;
}
if (akt >= fele && hossz < min)
{
min = hossz;
minid = id-1;
}
}
Console.WriteLine(min);
Console.WriteLine($"{minid - min + 2} {minid + 1}");
}
Console.ReadKey();
}
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 20/55 | ||||||
1 | Elfogadva | 0/0 | 30ms | 24784 KiB | |||
2 | Időlimit túllépés | 0/0 | 300ms | 11408 KiB | |||
3 | Részben helyes | 1/2 | 32ms | 25564 KiB | |||
4 | Elfogadva | 2/2 | 30ms | 25572 KiB | |||
5 | Elfogadva | 2/2 | 30ms | 25868 KiB | |||
6 | Elfogadva | 2/2 | 32ms | 26064 KiB | |||
7 | Elfogadva | 2/2 | 34ms | 26476 KiB | |||
8 | Elfogadva | 3/3 | 32ms | 26424 KiB | |||
9 | Elfogadva | 3/3 | 34ms | 26416 KiB | |||
10 | Elfogadva | 3/3 | 35ms | 26512 KiB | |||
11 | Időlimit túllépés | 0/3 | 266ms | 9032 KiB | |||
12 | Időlimit túllépés | 0/3 | 261ms | 9816 KiB | |||
13 | Időlimit túllépés | 0/3 | 277ms | 9840 KiB | |||
14 | Időlimit túllépés | 0/3 | 280ms | 12044 KiB | |||
15 | Időlimit túllépés | 0/3 | 268ms | 11808 KiB | |||
16 | Időlimit túllépés | 0/3 | 264ms | 12020 KiB | |||
17 | Időlimit túllépés | 0/3 | 264ms | 12328 KiB | |||
18 | Időlimit túllépés | 0/3 | 256ms | 13776 KiB | |||
19 | Részben helyes | 1/3 | 185ms | 36436 KiB | |||
20 | Részben helyes | 1/3 | 180ms | 36472 KiB | |||
21 | Időlimit túllépés | 0/3 | 284ms | 14144 KiB | |||
22 | Időlimit túllépés | 0/3 | 284ms | 13968 KiB |