|
|
back to boardWA#3 again... Posted by pasha 22 Mar 2013 18:32 I've tested all inputs from other themes, but still got wa in 3rd. Help, please! The algorithm based on the half-invariant idea. #include <iostream> #include <fstream> #include <string> #include <math.h> #include <sstream> using namespace std; int main(){ int n, m; cin >> n >> m; bool **e = new bool*[2*n]; for (int i=0; i<2*n; i++){ e[i] = new bool[2*n]; for (int j=0; j<2*n; j++){ e[i][j] = false; } } int v1, v2; for (int i=0; i<m; i++){ cin >> v1 >> v2; int tmp; if (v1 > v2){ tmp = v1; v1 = v2; v2 = tmp; } e[v1-1][v2-1] = true; e[v2-1][v1-1] = true; } int inv=0; for (int i=0; i<n; i++){ for (int j=i+1; j<n; j++){ if (e[i][j]) inv++; if (e[n+i][n+j]) inv++; } } int *t =new int[2*n]; for (int i=0; i<2*n; i++){ t[i] = i; } while (inv > 0){ int s = 0; for (int i=0; i<n; i++){ int i_out = 0; int i_in = 0; for (int k=0; k<n; k++){ if (e[t[i]][t[k]] || e[t[k]][t[i]]){ i_in++; } if (e[t[i]][t[k+n]] || e[t[k+n]][t[i]]){ i_out++; } } for (int j=n; j<2*n; j++){ int j_out = 0; int j_in = 0; for (int k=0; k<n; k++){ if (e[t[k+n]][t[j]] || e[t[j]][t[k+n]]){ j_in++; } if (e[t[k]][t[j]] || e[t[j]][t[k]]){ j_out++; } } if (e[t[i]][t[j]] || e[t[j]][t[i]]){ j_out--; j_out--; } if (i_in + j_in > i_out + j_out){ s++; inv -= (i_in + j_in - i_out - j_out); int tmp = t[i]; t[i] = t[j]; t[j] = tmp; } if (s == 1) break; } if (s == 1) break; } if (s == 0){ cout << "IMPOSSIBLE\n"; return 0; } } string tour1, tour2; tour1 = ""; tour2 = ""; for (int i=0; i<n; i++){ for (int j=i+1; j<n; j++){ if (t[i]>t[j]){ int tmp = t[i]; t[i] = t[j]; t[j] = tmp; } if (t[i+n]>t[j+n]){ int tmp = t[i+n]; t[i+n] = t[j+n]; t[j+n] = tmp; } } } for (int i=0; i<n; i++){ std::ostringstream ostr; ostr << (t[i]+1); std::string theNumberString = ostr.str(); tour1 = tour1 + theNumberString + " "; } for (int i=0; i<n; i++){ std::ostringstream ostr; ostr << (t[n+i]+1); std::string theNumberString = ostr.str(); tour2 = tour2 + theNumberString + " "; } cout << tour1 << endl << tour2 << endl; return 0; } |
|
|