fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. bool dp[101][1000001];
  4. int ara[100+1];
  5. int n;
  6. vector<int> get(int x){
  7. 	vector<int> cnt(n+1);
  8. 	for(int i = n; x&&i>=1; i--){
  9. 		if(x>=ara[i] && dp[i][x-ara[i]]){
  10. 			x -= ara[i];
  11. 			cnt[i]++;
  12. 			i++;
  13. 		}
  14. 	}
  15. 	return cnt;
  16. }
  17. int bin[1000006];
  18. char st[300];
  19. int main()
  20. {
  21. 	scanf("%d", &n);
  22. 	for(int i = 1; i<=n; i++){
  23. 		scanf("%d", &ara[i]);
  24. 	}
  25. 	dp[0][0] = 1;
  26. 	int lim = 1000000;
  27. 	for(int i = 1; i<=n; i++) dp[i][0] = 1;
  28. 	for(int i = 1; i<=n; i++){
  29. 		for(int j = 1; j<=ara[i]; j++) dp[i][j] = dp[i-1][j];
  30. 		for(int j = ara[i]; j<=lim; j++){
  31. 			dp[i][j] |= dp[i][j-ara[i]];
  32. 			dp[i][j] |= dp[i-1][j];
  33. 		}
  34. 	}
  35. 	// auto vt = get(56);
  36. 	// for(int i = 1; i<=n; i++){
  37. 	// 	cout << vt[i] << " ";
  38. 	// }
  39. 	int l = 0, r = -1;
  40.  
  41. 	for(int i = 1; i<=lim; i++){
  42. 		if(dp[n][i]) bin[++r] = i; 
  43. 	}
  44. 	while(l <= r){
  45. 		int mid = (l + r)/2;
  46. 		int val = bin[mid];
  47. 		auto vt = get(val);
  48. 		printf("1\n");
  49. 		for(int i = 1; i<=n; i++){
  50. 			if(i>1) printf(" ");
  51. 			printf("%d", vt[i]);
  52. 		}
  53. 		printf("\n");
  54. 		fflush(stdout);
  55. 		scanf("%s", st);
  56. 		if(st[0]=='g'){
  57. 			l = mid + 1;
  58. 		} else if(st[0]=='r'){
  59. 			r = mid - 1;
  60. 		} else{
  61. 			printf("2\n%d\n", val);
  62. 			fflush(stdout);
  63. 			return 0;
  64. 		}
  65. 	}
  66. 	swap(l, r);
  67. 	if(bin[l]==bin[r]-2){
  68. 		printf("2\n%d\n", bin[l]+1);
  69. 		fflush(stdout);
  70. 		return 0;
  71. 	}
  72. 	printf("2\n-1\n");
  73. 	fflush(stdout);
  74.  
  75. 	return 0;
  76. }
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
-1
https://ideone.com/QoouGs
language:
C++14 (gcc 8.3)
created:
4 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!