0
Your rating: None

CodeChef submission 495081 (C++ 4.3.2)

CodeChef submission 495081 (C++ 4.3.2) plaintext list. Status: WA, problem SEQUENCE, contest . By pdwd (pdwd), 2011-03-21 20:32:47.
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <iostream>
  4. #include <fstream>
  5. #include <sstream>
  6. #include <set>
  7. #include <map>
  8. #include <vector>
  9. #include <list>
  10. #include <algorithm>
  11. #include <cstring>
  12. #include <cmath>
  13. #include <string>
  14. #include <queue>
  15. #include <bitset>		//UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
  16. #include <cassert>
  17. #include <iomanip>		//do setprecision
  18. #include <ctime>
  19. using namespace std;
  20. #define PB push_back
  21. #define LL long long
  22. #define ULL unsigned LL
  23. #define LD long double
  24.  
  25. #define MR 1<<15
  26. int w[MR], ktory[MR];
  27.  
  28. //budowa kodu Gray'a - w[0] = 0
  29. //w[i] = {jesli i nieparzyste, w[i-1] z zamienionym ostatnim bitem, wpp bierzemy j - pierwszy od prawej
  30. //zapalony bit w w[i-1] i zamieniamy bit na pozycji j+1 -> w lewo
  31.  
  32. void gray(int dl)	//generuj ciag gray'a o zadanej dlugosci
  33. {
  34. 	//w[0] = 0
  35. 	for(int i = 1; i < dl; i++)
  36. 		if(i & 1)
  37. 			w[i] = w[i-1]^1;
  38. 		else
  39. 			w[i] = w[i-1]^(1<<(__builtin_ctz(w[i-1])+1));
  40. }//gray
  41.  
  42. void gen(int dl)	//wyznacza ciag bitow, ktore sie zmieniaja przy generacji ciagu graya
  43. {
  44. 	for(int i = 1; i < dl; i++)
  45. 		if(i & 1)
  46. 			ktory[i-1] = 0;
  47. 		else
  48. 			ktory[i-1] = __builtin_ctz(w[i-1])+1;	//mamy wczesniej wygenerowany kod graya
  49. }//gen
  50.  
  51. int main()
  52. {
  53. 	int tests;
  54. 	scanf("%d", &tests);
  55. 	for(int c = 0; c < tests; c++)
  56. 	{
  57. 		int n, a, b, dl;
  58. 		scanf("%d%d%d", &n, &a, &b);
  59. 		dl = 1 << n;
  60. 		if(__builtin_popcount(a^b) > 1)	//mozemy normalny kod graya zrobic
  61. 			gray(dl);
  62. 		else
  63. 		{
  64. 			if(n < 3)	//w tej sytuacji nie da sie wygenerowac
  65. 			{
  66. 				printf("-1\n");
  67. 				continue;
  68. 			}			
  69. 			gray(dl);
  70. 			if(w[1] == (a^b) || w[dl-1] == (a^b))	//trzeba zmienic troche kod graya, 0 stoi obok a^b
  71. 			{
  72. 				gen(dl);
  73. 				//wyznacz 2^k - ktory nie sasiaduje z 0
  74. 				int k;
  75. 				for(int i = 0; i < n; i++)
  76. 					if((1<<i) != w[1] && (1<<i) != w[dl-1])
  77. 					{
  78. 						k = i;
  79. 						break;
  80. 					}
  81. 				int j = __builtin_clz(a^b);	//2^j == a^b
  82. 				//zamien wystapienia bitow k na j i j na k
  83. 				for(int i = 0; i < dl-1; i++)
  84. 					if(ktory[i] == j)
  85. 						ktory[i] = k;
  86. 					else if(ktory[i] == k)
  87. 						ktory[i] = j;
  88. 				//odtworz ciag
  89. 				for(int i = 1; i < dl; i++)
  90. 					w[i] = w[i-1]^(1<<ktory[i-1]);				
  91. 			}
  92. 			//wynik trzeba sksorowac przez a
  93. 			for(int i = 0; i < dl; i++)
  94. 				w[i] ^= a;
  95. 		}		
  96. 		//wypisz wynik
  97. 		for(int i = 0; i < dl; i++)
  98. 			printf("%d ", w[i]);
  99. 		printf("\n");
  100. 	}
  101. 	return 0;
  102. }

Comments