Cod sursa(job #3286809)

Utilizator maxtraAlex Deonise maxtra Data 14 martie 2025 18:11:43
Problema Grozavesti Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("grozavesti.in");
ofstream fout("grozavesti.out");

int n; // dimensiunea matricei
int k; // contor pentru stocarea operatiilor
int v[305]; // vector care tine minte elementele de pe diagonala principala
int s[608]; // retin perechile de interschimbari
int nr; // contorul numarului de interschimbari
int ok, y, z, maxim, pmax, x, aux;



int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            fin >> x;
            
            if (i == j) {
                v[i] = x; // stocam doar diagonala principala
            }
    }
    }
    
    
    // sortez descrescator diagonala principala
    // parcurg vectorul de la stanga
    // se cauta cel mai mare element din [1, i] si se retine pozitia acestuia in pmax
    // daca pmax nu este deja pozitia i, atunci se interschimba pozitiile
    // detaliile le retin in s
    for (int i = n; i >= 2; i--) {
        maxim = v[1];
        pmax = 1;
        
        for (int j = 2; j <= i; j++) {
            if (maxim < v[j]) {
                maxim = v[j];
                pmax = j;
            }
        }
    
        if (pmax != i) {
            aux = v[pmax];
            v[pmax] = v[i];
            v[i] = aux;
            nr++;
            s[++k] = pmax;
            s[++k] = i;
        }
    }
    
    // scriem in fisier numarul total de interschimbari (de doua ori nr,
    // deoarece fiecare interschimbare de coloane este urmata de un schimb de linii)
    // parcurg vectorul s, unde fiecare pereche s[i * 2 - 1] si s[i * 2] reprezinta o operatie
    // de interschimbare
    // se face mai intai operatia de inteschimbare pe coloane si apoi pe linii
    fout << nr * 2 << '\n';
    for (int i = 1; i <= nr; i++) {
        fout << "C " << s[i * 2 - 1] << " " << s[i * 2] << '\n';
        fout << "L " << s[i * 2 - 1] << " " << s[i * 2] << '\n';
        
    }
    

    return 0;
}