fork download
copy 
  1. using static IO;
  2. public class IO
  3. {
  4. public static IO Cin = new();
  5. public static StreamReader reader = new(Console.OpenStandardInput());
  6. public static StreamWriter writer = new(Console.OpenStandardOutput());
  7. public static implicit operator string(IO _) => reader.ReadLine();
  8. public static implicit operator char[](IO _) => reader.ReadLine().ToArray();
  9. public static implicit operator int(IO _) => int.Parse(reader.ReadLine());
  10. public static implicit operator double(IO _) => double.Parse(reader.ReadLine());
  11. public static implicit operator string[](IO _) => reader.ReadLine().Split();
  12. public static implicit operator int[](IO _) => Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
  13. public void Deconstruct(out int a, out int b) { int[] r = Cin; (a, b) = (r[0], r[1]); }
  14. public void Deconstruct(out int a, out int b, out int c) { int[] r = Cin; (a, b, c) = (r[0], r[1], r[2]); }
  15. public static IEnumerable<int> MakeRange(int start, int count) => Enumerable.Range(start, count);
  16. public static T[] MakeArray<T>(int count) where T : new() => MakeRange(0, count).Select(_ => new T()).ToArray();
  17. public static object? Cout { set { writer.Write(value); } }
  18. public static object? Coutln { set { writer.WriteLine(value); } }
  19. public static void Main() { Program.Coding(); writer.Flush(); }
  20. }
  21. class Program
  22. {
  23.     public static void Coding()
  24.     {
  25.         checked
  26.         {
  27.             (int applicantCount, int groupCount, int groupLimit) = Cin;
  28.             int[][] graph = MakeRange(0, applicantCount).Select(_ => ((int[])Cin)[1..]).ToArray();
  29.  
  30.             int[] score = Cin;
  31.             int[] matchGroup = new int[groupCount * groupLimit]; Array.Fill(matchGroup, -1);
  32.             bool[] visited = new bool[matchGroup.Length];
  33.             bool Dfs(int me)
  34.             {
  35.                 foreach (int group in graph[me])
  36.                 {
  37.                     for (int end = group * groupLimit, g = end - groupLimit; g < end; g++)
  38.                     {
  39.                         if (visited[g]) continue;
  40.                         visited[g] = true;
  41.  
  42.                         if (matchGroup[g] < 0 || Dfs(matchGroup[g]))
  43.                         {
  44.                             matchGroup[g] = me;
  45.                             return true;
  46.                         }
  47.                     }
  48.                 }
  49.                 return false;
  50.             }
  51.             foreach (int me in MakeRange(0, applicantCount).OrderByDescending(i => score[i]))
  52.             {
  53.                 Array.Fill(visited, false);
  54.                 Dfs(me);
  55.             }
  56.  
  57.             foreach(var join in MakeRange(0, groupCount).Select(g => matchGroup.Skip(g*groupLimit).Take(groupLimit).Where(m => m >= 0)))
  58.             {
  59.                 LinkedList<int> output =new(join.Select(m => m+1));
  60.                 output.AddFirst(output.Count);
  61.                 Coutln = string.Join(' ', output);
  62.             }
  63.         }
  64.     }
  65. }
Success #stdin #stdout 0.11s 31776KB
comments (?)
stdin
copy 
5 2 2
1 1
2 1 2
1 1
1 1
1 2
5 4 3 2 1
stdout
copy 
2 3 1
2 5 2
https://ideone.com/Daaf5c
2 1 3
2 2 5
language:
C# (NET 6.0)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!