Created
April 24, 2020 13:56
-
-
Save SilviuCristian45/452253d458d68870c17f362ea9123282 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <fstream> | |
using namespace std; | |
ifstream fin("pachete_multe.in"); | |
ofstream fout("pachete_multe.out"); | |
//Strategie 1 O(N^2) | |
//Cat timp sirul nu e completat 1,2,...n | |
//1)Iau elementul curent, il mut intr-o casuta goala (n+1) | |
//2)Iau acel sir[j] pa_int care sir[j] == pozitie_curent index | |
//3)pe pozitia elementului curent pun pe sir[j] | |
//4)Pe fosta pozitie a lui sir[j] pun elementul de pe casuta goala(n+1) | |
//Gata | |
//Nu functioneaza strategia 1. Gandeste alta | |
//Strategie 2 ? - Discord | |
int N,a[100000], nr_mutari = 0,pozitii[100000]; | |
pair <int,int> mutari[100000]; | |
void citeste() | |
{ | |
fin >> N; | |
for(int i = 1; i <= N; i++) | |
fin>>a[i]; | |
a[N+1] = 0;//casuta goala | |
} | |
void initializare_pozitii() | |
{ | |
for(int i = 1; i <= N; i++) | |
{ | |
pozitii[a[i]] = i; | |
} | |
pozitii[0] = N+1; | |
} | |
void rezolvare() | |
{ | |
int i = 1; | |
int index_casuta_goala = N+1; | |
//initializez array-ul de pozitii . pozitii[i] = indexul la care se afla valoarea i in sirul data | |
initializare_pozitii(); | |
//for(int i = 0; i <= N; i++) | |
//{ | |
// cout << pozitii[i] << " "; | |
//} | |
//cout << endl; | |
while(i <= N) | |
{ | |
//punem conditiile astea pt ca in cazul in care a[i] == i | |
//sau a[i] == 0 , nu mai e nevoie sa facem mutari aiurea | |
//daca a[i] == 0 singura mutare ce trebuie facuta e sa | |
if(a[i] != i && a[i] != 0) | |
{ | |
//se muta de pe pozitia i pe pozitia casutei goale | |
a[index_casuta_goala] = a[i]; | |
mutari[nr_mutari++] = make_pair(i,index_casuta_goala); | |
//vedem care e pozitia reala in sir unde a[j] == i | |
pozitii[a[index_casuta_goala]] = index_casuta_goala; | |
//adaugam inca o mutare in sirul de mutari . | |
//mutarea j - i | |
index_casuta_goala = pozitii[i]; | |
a[pozitii[i]] = 0; | |
mutari[nr_mutari++] = make_pair(index_casuta_goala,i); | |
a[i] = i; | |
pozitii[0] = pozitii[i]; | |
pozitii[i] = i; | |
} | |
else | |
{ | |
//in cazul asta e nevoie de o mutare mai simpla | |
//direct de pe pozitia pe care se afla valoarea i | |
//pe pozitia asta goala si prafuita | |
if(a[i] == 0) | |
{ | |
mutari[nr_mutari++] = make_pair(pozitii[i],i); | |
a[i] = i; | |
index_casuta_goala = pozitii[i]; | |
pozitii[i] = i; | |
pozitii[0] = index_casuta_goala; | |
a[index_casuta_goala] = 0; | |
/* | |
for(int j = 1; j <= N+1; j++) | |
{ | |
if(a[j] == i) | |
{ | |
mutari[nr_mutari++] = make_pair(j,i); | |
a[i] = i; | |
index_casuta_goala = j; | |
a[j] = 0; | |
break; | |
} | |
} | |
*/ | |
} | |
} | |
//for(int p = 0; p <= N; p++) | |
//{ | |
// cout << pozitii[p] << " "; | |
//} | |
//cout << endl; | |
i++; | |
} | |
fout << nr_mutari<<endl; | |
for(int i = 0; i < nr_mutari; i++) | |
{ | |
fout << mutari[i].first << " " << mutari[i].second << endl; | |
} | |
} | |
int main() | |
{ | |
citeste(); | |
rezolvare(); | |
fin.close(); | |
fout.close(); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment