fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <string.h>
  6. #include <vector>
  7. using namespace std;
  8.  
  9. int row1[100001];
  10. int row2[100001];
  11. int row3[100001];
  12. int n;
  13.  
  14. vector<int> Lists[100001];
  15. int Seen[4][100001];
  16. bool Removed[100001];
  17. vector<int> ToKill;
  18. bool TFO[100001];
  19. int ctr;
  20.  
  21. void Try(int x)
  22. {
  23.     if (TFO[x])
  24.     return;
  25.     if (Seen[1][x]!=0 && Seen[2][x]!=0 && Seen[3][x]!=0)
  26.     return;
  27.  
  28.     TFO[x]=true;
  29.  
  30.     ToKill.push_back(x);
  31.  
  32.     return;
  33. }
  34.  
  35. void RemoveColumn(int x)
  36. {
  37.     if (Removed[x])
  38.     return;
  39.  
  40.     ctr++;
  41.  
  42.     Removed[x]=true;
  43.  
  44.     Seen[1][ row1[x] ]--;
  45.     Seen[2][ row2[x] ]--;
  46.     Seen[3][ row3[x] ]--;
  47.  
  48.     Try(row1[x]); ///Other potential forced columns may come if some of the numbers in this one
  49.     Try(row2[x]); ///become extinct from some row, so the three checks are enough
  50.     Try(row3[x]); ///to find the newly forced columns
  51.  
  52.     return;
  53. }
  54.  
  55. int FastSolve()
  56. {
  57.     int i;
  58.     int uk;
  59.     int V;
  60.  
  61.     ctr=0;
  62.  
  63.     for (i=1;i<=n;i++)
  64.     {
  65.         Lists[ row1[i] ].push_back(i); ///The lists hold the rows in which each number is
  66.         Lists[ row2[i] ].push_back(i);
  67.         Lists[ row3[i] ].push_back(i);
  68.  
  69.         Seen[1][ row1[i] ]++; ///The "Seen" array holds the amount of times we've seen a number on some row
  70.         Seen[2][ row2[i] ]++;
  71.         Seen[3][ row3[i] ]++;
  72.     }
  73.  
  74.     for (i=1;i<=n;i++)
  75.     {
  76.         Try(i); ///Try checks whether a number is present in all three rows
  77.     }
  78.  
  79.     uk=0;
  80.  
  81.     while(uk<ToKill.size()) ///While there are numbers not present in all three rows
  82.     {
  83.         V=ToKill[uk];
  84.  
  85.         for (i=0;i<Lists[V].size();i++) ///Remove all columns that contain those numbers
  86.         {
  87.             RemoveColumn(Lists[V][i]);
  88.         }
  89.  
  90.         uk++;
  91.     }
  92.  
  93.     return ctr;
  94. }
  95.  
  96. int main()
  97. {
  98.     //freopen("test.txt","r",stdin);
  99.  
  100.     int i;
  101.  
  102.     scanf("%d",&n);
  103.  
  104.     for (i=1;i<=n;i++)
  105.     {
  106.         scanf("%d",&row1[i]);
  107.     }
  108.     for (i=1;i<=n;i++)
  109.     {
  110.         scanf("%d",&row2[i]);
  111.     }
  112.     for (i=1;i<=n;i++)
  113.     {
  114.         scanf("%d",&row3[i]);
  115.     }
  116.  
  117.     printf("%d\n",FastSolve());
  118.  
  119.     return 0;
  120. }
  121.  
Success #stdin #stdout 0s 7248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/IL5p0c
language:
C++ (gcc 8.3)
created:
9 years 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!