fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define out(a) copy(a.begin(),a.end(),ostream_iterator<int>(cout," "))
  5. class Sortish {
  6. public:
  7. 	int sum;
  8. 	vector<int> arr;
  9. 	vector<int> pos, want, have;
  10. 	int n;
  11. 	int inter[2002];
  12. 	int val[15][15];
  13. 	map<int, ll> dp[(1<<14)];
  14.  
  15. 	int ls(int indx) {
  16. 		return indx & (-indx);
  17. 	}
  18. 	int get(int indx) {
  19. 		int res = 0;
  20. 		for (; indx > 0; indx -= ls(indx))
  21. 			res += inter[indx];
  22. 		return res;
  23. 	}
  24. 	void update(int indx, int val) {
  25. 		for (; indx <= n; indx += ls(indx))
  26. 			inter[indx] += val;
  27. 	}
  28. 	ll solve(int indx, int mask, int need) {
  29. 		if (need < 0)
  30. 			return 0;
  31. 		if (indx == (int) want.size())
  32. 			return need == 0;
  33. 		if (dp[mask].find(need) != dp[mask].end())
  34. 			return dp[mask][need];
  35. 		ll res = 0;
  36. 		for (size_t i = 0; i < want.size(); ++i) {
  37. 			if (mask & (1 << i))
  38. 				continue;
  39. 			int tmp = val[indx][i];
  40. 			for (size_t j = 0; j < i; ++j) {
  41. 				if (mask & (1 << j))
  42. 					++tmp;
  43. 			}
  44. 			res += solve(indx + 1, mask | (1 << i), need - tmp);
  45. 		}
  46. 		return dp[mask][need] = res;
  47. 	}
  48. 	long long ways(int sortedness, vector<int> seq) {
  49. 		n = seq.size();
  50. 		arr = seq;
  51. 		map<int, int> cnt;
  52. 		for (int i = 0; i < n; ++i)
  53. 			if (arr[i])
  54. 				cnt[arr[i]]++;
  55. 			else
  56. 				pos.push_back(i);
  57. 		for (int i = 1; i <= n; ++i)
  58. 			if (cnt.find(i) != cnt.end())
  59. 				have.push_back(i);
  60. 			else
  61. 				want.push_back(i);
  62. 		int ps=0;
  63. 		for (int i = 0; i < n; ++i) {
  64. 			if (arr[i]) {
  65. 				sum += get(arr[i] - 1);
  66. 				update(arr[i], 1);
  67. 			} else {
  68. 				for (size_t j = 0; j < want.size(); ++j) {
  69. 					val[ps][j] += get(want[j] - 1);
  70. 					for (int k = i + 1; k < n; ++k) {
  71. 						if (arr[k] > want[j])
  72. 							++val[ps][j];
  73. 					}
  74. 				}
  75. 				++ps;
  76. 			}
  77. 		}
  78. 		return solve(0, 0, sortedness - sum);
  79. 	}
  80. };
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/lib/gcc/i586-linux-gnu/5/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/eeCNuu
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!