Advertisement
nicuvlad76

Untitled

Feb 5th, 2023
692
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.92 KB | None | 0 0
  1. /*
  2. Complexitate O(N * N + N * M)
  3. Sursa foloseste elemente de STL si C++11, dar acestea nu sunt critice in rezolvarea problemei.
  4. Pentru detalii despre anumite functii sau tipuri de date, puteti consulta documentatia pe cplusplus.com.
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. int main() {
  11.     ifstream cin("admitere.in");
  12.     ofstream cout("admitere.out");
  13.  
  14.     int tip, n, m; cin >> tip >> n >> m;
  15.  
  16.     vector<vector<int>> fixedGrades(2, vector<int> (m, 0));
  17.     vector<vector<int>> currGrades(n, vector<int> (2, 0));
  18.    
  19.     // 0 = REAL, 1 = UMAN
  20.  
  21.     for(int i = 0; i < 2; ++i)
  22.        for(int j = 0; j < m; ++j)
  23.            cin >> fixedGrades[i][j]; // cele M note deja existente la fiecare clasa
  24.  
  25.     for(int i = 0; i < n; ++i)
  26.        cin >> currGrades[i][0] >> currGrades[i][1]; // notele celor N elevi privilegiati
  27.    
  28.     vector<vector<int>> frontAlready(2, vector<int> (n, 0));
  29.     vector<vector<int>> p(2, vector<int> (n, 0));
  30.    
  31.     // Precalculam p[C][index] = care este al index-lea elev privilegiat in ordine
  32.     // crescatoare, daca ii sortam dupa nota pentru clasa C
  33.  
  34.     for(int c = 0; c < 2; ++c) {  
  35.         for(int i = 0; i < n; ++i)
  36.             p[c][i] = i;
  37.         sort(p[c].begin(), p[c].end(), [&] (int a, int b) {
  38.             return currGrades[a][c] < currGrades[b][c];
  39.         });
  40.     }
  41.    
  42.     // Precalculam frontAlready[C][E] = cate din cele M note deja existente la clasa C
  43.     // sunt mai mari decat nota elevului privilegiat cu numarul E la clasa C
  44.    
  45.     for(int c = 0; c < 2; ++c)
  46.         for(int i = 0; i < n; ++i)
  47.             for(int j = 0; j < m; ++j)
  48.                 if(fixedGrades[c][j] > currGrades[i][c])
  49.                     frontAlready[c][i]++;
  50.    
  51.     int bestAns = 0;
  52.     string bestConfig(n, 'X');
  53.     string label = "RU";
  54.    
  55.     // Functia realityCheck preia un string cu optiunile de inscriere ale celor N elevi
  56.     // si il "aduce la realitate", punand 'X' in dreptul elevilor care nu sunt admisi
  57.     // la clasa aleasa. Complexitatea functiei este O(N).
  58.  
  59.     auto realityCheck = [&] (string config) -> string {
  60.         for(int c = 0; c < 2; ++c) {
  61.             int greaterFriends = 0;
  62.             for(int i = n - 1; i >= 0; --i) { // parcurgem elevii privilegiati inscrisi la clasa c in ordine descrescatoare dupa nota
  63.                 if(config[p[c][i]] != label[c])
  64.                     continue;
  65.  
  66.                 // greaterFriends = cati elevi privilegiati inscrisi la clasa c au fost admisi deja
  67.                 // frontAlready[..] = cati elevi din cei M initiali aveau note mai mari decat cel curent
  68.                 // pozitia elevului curent este data de suma acestor doua valori + 1
  69.                 // daca este >= m, elevul este respins
  70.  
  71.                 if(greaterFriends + frontAlready[c][p[c][i]] >= m)
  72.                     config[p[c][i]] = 'X';
  73.                 greaterFriends++;
  74.             }
  75.         }
  76.         return config;
  77.     };
  78.    
  79.     // Cerinta 1
  80.  
  81.     for(int c = 0; c < 2; ++c) {
  82.         string config(n, label[c]); // toti elevii se inscriu la clasa c
  83.         config = realityCheck(config); // config ne spune acum care elevi au ramas efectiv admisi la clasa c
  84.  
  85.         int temp = 0;
  86.         for(int i = 0; i < n; ++i)
  87.             if(config[i] != 'X')
  88.                 ++temp;
  89.  
  90.         if(temp > bestAns) { // actualizam raspunsul cel mai bun
  91.             bestAns = temp;
  92.             bestConfig = config;
  93.         }
  94.     }
  95.  
  96.     if(tip == 1) {
  97.         cout << bestAns << "\n";
  98.         cout << bestConfig << "\n";
  99.         return 0;
  100.     }
  101.    
  102.  
  103.     //Cerinta 2
  104.  
  105.     const int REAL = 0, UMAN = 1;
  106.  
  107.     for(int minReal = 0; minReal < n; ++minReal) { // fixam ultimul privilegiat admis la Real
  108.         string config(n, 'X');
  109.         config[minReal] = label[REAL];
  110.        
  111.         int space = m - 1;
  112.         for(int i = 0; i < m; ++i)
  113.             if(fixedGrades[REAL][i] > currGrades[minReal][REAL]) // mai putem pune maxim "space" privilegiati la Real
  114.                 space--;
  115.        
  116.         for(int i = 0; i < n; ++i) { // parcurgem ceilalti N - 1 elevi in ordine crescatoare dupa nota de la UMAN
  117.             if(p[UMAN][i] == minReal)
  118.                 continue;
  119.             if(currGrades[p[UMAN][i]][REAL] > currGrades[minReal][REAL] && space > 0) { // daca elevul are nota de Real > minimul fixat si mai avem loc, il punem la real.
  120.                 config[p[UMAN][i]] = label[REAL];
  121.                 space--;
  122.             } else { // altfel se inscrie la uman
  123.                 config[p[UMAN][i]] = label[UMAN];
  124.             }
  125.         }
  126.        
  127.         config = realityCheck(config); // aducem configuratia la realitate
  128.  
  129.         int temp = 0;
  130.         for(int i = 0; i < n; ++i)
  131.             if(config[i] != 'X')
  132.                 temp++;
  133.        
  134.         if(temp > bestAns) {
  135.             bestAns = temp;
  136.             bestConfig = config;
  137.         }
  138.     }
  139.        
  140.     cout << bestAns << "\n";
  141.     cout << bestConfig << "\n";
  142. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement