fork(4) download 
  1. /*
  2. * @problem: ICPC16F
  3. */
  4.  
  5. #include <iostream>
  6. #include <cstring>
  7. #include <cstdio>
  8. #include <iomanip>
  9. #include <cmath>
  10. #include <limits.h>
  11. #include <vector>
  12. #include <map>
  13. #include <bitset>
  14. #include <string>
  15. #include <iterator>
  16. #include <set>
  17. #include <utility>
  18. #include <queue>
  19. #include <numeric>
  20. #include <functional>
  21. #include <ctype.h>
  22. #include <stack>
  23. #include <algorithm>
  24. #include <cstdlib>
  25. #define MAX 100100
  26. #define mod 1000000007LL
  27. #define bitcnt(x) __builtin_popcountll(x)
  28. #define MS0(x) memset(x, 0, sizeof(x))
  29. #define MS1(x) memset(x, -1, sizeof(x))
  30. #define ll long long int
  31. #define mp(x, y) make_pair(x, y)
  32. #define pii pair<int, int>
  33. #define pll pair<ll, ll>
  34. #define in(x) scanf("%lld", &x)
  35. #define ind(x) scanf("%d", &x)
  36. #define ins(x) scanf("%s", x)
  37. #define pr(x) printf("%lld\n", x)
  38. #define prd(x) printf("%d\n", x)
  39. #define pi acos(-1.0)
  40. #define ff first
  41. #define ss second
  42.  
  43. using namespace std;
  44. int n, m, d, D, inL[110], inR[110];
  45. bool vis[110][110];
  46. vector<pii> edge;
  47.  
  48. int main() {
  49. 	#ifdef LOCAL_PROJECT
  50. 		freopen("../input.txt", "r", stdin);
  51. 		freopen("../output1.txt", "w", stdout);
  52. 	#endif
  53. 	// ios_base::sync_with_stdio(0);
  54.     // cin.tie(0);
  55. 	int t;
  56. 	ind(t);
  57. 	while (t--) {
  58. 		int M;
  59. 		edge.clear();
  60. 		priority_queue<pii, vector<pii>, greater<pii> > q;
  61. 		MS0(inL);
  62. 		MS0(inR);
  63. 		MS0(vis);
  64. 		ind(n);
  65. 		ind(m);
  66. 		ind(d);
  67. 		ind(D);
  68. 		M = m;
  69. 		//cerr << n << " " << m << " " << d << " " << D << endl;
  70. 		if ((m < (d * n)) || (m > (D * n))) {
  71. 			printf("-1\n");
  72. 			continue;
  73. 		}
  74. 		int c = m / n;
  75. 		bool flag = 0;
  76. 		for (int i = 1; i <= n && m > 0; i++) {
  77. 			while(!q.empty())
  78. 				q.pop();
  79. 			for (int j = 1; j <= n; j++)
  80. 				q.push(mp(inR[j], j));
  81. 			while(inL[i] < c && !q.empty() && m > 0) {
  82. 				pii cur = q.top();
  83. 				q.pop();
  84. 				if(vis[i][cur.ss] || inR[i] == c)
  85. 					continue;
  86. 				edge.push_back(mp(i, cur.ss));
  87. 				inR[cur.ss]++;
  88. 				vis[i][cur.ss] = 1;
  89. 				inL[i]++;
  90. 				m--;
  91. 			}
  92. 		}
  93. 		for (int i = 1; i <= n && m > 0; i++) {
  94. 			int c = 0;
  95. 			while(!q.empty())
  96. 				q.pop();
  97. 			for (int j = 1; j <= n; j++)
  98. 				q.push(mp(inR[j], j));
  99. 			while(inL[i] < D && !q.empty() && m > 0) {
  100. 				pii cur = q.top();
  101. 				q.pop();
  102. 				if(vis[i][cur.ss] || inR[cur.ss] == D)
  103. 					continue;
  104. 				edge.push_back(mp(i, cur.ss));
  105. 				inR[cur.ss]++;
  106. 				vis[i][cur.ss] = 1;
  107. 				inL[i]++;
  108. 				m--;
  109. 			}
  110. 		}
  111. 		for (int i = 1; i <= n; i++) {
  112. 			//cout << in[i] << " ";
  113. 			if (inL[i] < d || inL[i] > D || inR[i] < d || inR[i] > D) {
  114. 				flag = 1;
  115. 			}
  116. 		}
  117. 		//cout << endl;
  118. 		if (m != 0 || flag) {
  119. 			printf("-1\n");
  120. 			continue;
  121. 		}
  122. 		/* 
  123. 			 The below line is an extra output for checker function only.
  124. 			 It was not added in the submission during the contest.
  125. 		*/
  126. 		cout << n << " " << M << " " << d << " " << D << endl; 
  127. 		for (int i = 0; i < edge.size(); i++) {
  128. 			printf("%d %d\n", edge[i].ff, edge[i].ss);
  129. 		}
  130. 	}
  131. 	return 0;
  132. }
Runtime error #stdin #stdout 0s 3484KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/nV20zD
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!