Submission #993338
Source Code Expand
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading;
using Pair = System.Collections.Generic.KeyValuePair<int, int>;
class Program
{
public Program() { }
static void Main(string[] args)
{
new Program().prog();
}
Scanner cin;
const int MOD = 1000000007;
const int INF = int.MaxValue - 10;
const long INFL = long.MaxValue - 10;
const double EPS = 1e-7;
const double PI = 3.1415926536;
int N,M;
int[] X;
int[] num, pair;
void prog()
{
cin = new Scanner();
int[,] dir8 = new int[8, 2] { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, { 0, 1 }, { 1, -1 }, { 1, 0 }, { 1, 1 } };
int[,] dir4 = new int[4, 2] { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };
N = cin.nextInt(); // 10^5
M = cin.nextInt(); // 10^5
num = new int[M];
pair = new int[M];
X = new int[N];
for (int i = 0; i < N; i++)
{
X[i] = cin.nextInt(); // 10^5
num[X[i] % M]++;
}
// ペア後回し
Array.Sort(X);
for (int i = 0; i < N - 1; i++)
{
if (X[i] == X[i + 1])
{
pair[X[i] % M]++;
i++;
}
}
long ans = 0;
for (int i = 1; i < (M + 1) / 2; i++)
{
if (num[i] <= num[M - 1])
{
int min = num[i];
//pair[i] = 0;
pair[M - i] -= (Math.Max(min - (num[M - i] - pair[M - i] * 2), 0) + 1) / 2;
ans += min;
ans += pair[M - i];
}
else
{
int min = num[M - i];
pair[i] -= (Math.Max(min - (num[i] - pair[i] * 2), 0) + 1) / 2;
//pair[M - i] = 0;
ans += min;
ans += pair[i];
}
}
ans += num[0] / 2;
if (M % 2 == 0)
{
ans += num[M / 2] / 2;
}
Console.WriteLine(ans);
}
}
class Scanner
{
string[] s;
int i;
char[] cs = new char[] { ' ' };
public Scanner()
{
s = new string[0];
i = 0;
}
public string next()
{
if (i < s.Length) return s[i++];
string st = Console.ReadLine();
while (st == "") st = Console.ReadLine();
s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
i = 0;
return next();
}
public int nextInt()
{
return int.Parse(next());
}
public long nextLong()
{
return long.Parse(next());
}
public double nextDouble()
{
return double.Parse(next());
}
}
Submission Info
Submission Time |
|
Task |
D - Pair Cards |
User |
furuya1223 |
Language |
C# (Mono 4.6.2.0) |
Score |
0 |
Code Size |
2304 Byte |
Status |
WA |
Exec Time |
81 ms |
Memory |
10584 KB |
Judge Result
Set Name |
sample |
all |
Score / Max Score |
0 / 0 |
0 / 700 |
Status |
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt |
all |
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
23 ms |
2904 KB |
01-02.txt |
AC |
77 ms |
9688 KB |
01-03.txt |
AC |
77 ms |
9688 KB |
01-04.txt |
AC |
77 ms |
9688 KB |
01-05.txt |
AC |
77 ms |
9688 KB |
01-06.txt |
AC |
77 ms |
9688 KB |
01-07.txt |
AC |
77 ms |
9688 KB |
01-08.txt |
AC |
77 ms |
9688 KB |
01-09.txt |
AC |
77 ms |
9816 KB |
01-10.txt |
WA |
78 ms |
10072 KB |
01-11.txt |
AC |
81 ms |
10584 KB |
01-12.txt |
AC |
67 ms |
9816 KB |
01-13.txt |
AC |
67 ms |
10072 KB |
01-14.txt |
AC |
76 ms |
9688 KB |
01-15.txt |
AC |
77 ms |
9688 KB |
01-16.txt |
AC |
76 ms |
9688 KB |
01-17.txt |
AC |
77 ms |
9688 KB |
01-18.txt |
AC |
76 ms |
9816 KB |
01-19.txt |
AC |
77 ms |
9816 KB |
01-20.txt |
AC |
80 ms |
10584 KB |
01-21.txt |
AC |
75 ms |
9688 KB |
01-22.txt |
AC |
75 ms |
9688 KB |
01-23.txt |
AC |
76 ms |
9688 KB |
01-24.txt |
WA |
75 ms |
9688 KB |
01-25.txt |
AC |
76 ms |
9944 KB |
01-26.txt |
AC |
78 ms |
10584 KB |
01-27.txt |
AC |
57 ms |
7000 KB |
01-28.txt |
AC |
23 ms |
3800 KB |
01-29.txt |
AC |
21 ms |
3032 KB |
01-30.txt |
AC |
21 ms |
3416 KB |
sample-01.txt |
AC |
20 ms |
2648 KB |
sample-02.txt |
AC |
20 ms |
2648 KB |