fork download
copy 
  1. // #define ONLINE_JUDGE
  2.  
  3. // Interactive problem solution template
  4.  
  5. #if defined(ONLINE_JUDGE)
  6. #define _SECURE_SCL 0
  7. #endif
  8.  
  9. #include <iostream>
  10. #include <iomanip>
  11. #include <string>
  12. #include <sstream>
  13. #include <fstream>
  14. #include <algorithm>
  15. #include <vector>
  16. #include <deque>
  17. #include <set>
  18. #include <map>
  19. #include <functional>
  20. #include <memory>
  21. #include <cmath>
  22. #include <climits>
  23. #include <numeric>
  24. #include <tuple>
  25. #include <random>
  26. #include <memory.h>
  27. #include <stdint.h>
  28.  
  29. #if !defined(__GNUC__)
  30. #else // !defined(__GNUC__)
  31. #define _CrtDbgBreak() __builtin_trap()
  32. #endif // !defined(__GNUC__)
  33.  
  34. #if defined(ONLINE_JUDGE)
  35. #define LOCAL_TEST 0
  36. #else
  37. #define LOCAL_TEST 1
  38. #endif
  39.  
  40. template<typename T1, typename T2> auto Endl(std::basic_ostream<T1, T2>& ostr) -> decltype(std::endl<T1, T2>(ostr)) {
  41.     return std::endl<T1, T2>(ostr);
  42. }
  43.  
  44. #if LOCAL_TEST
  45. struct AssertsCounter
  46. {
  47. 	AssertsCounter(): counter(0) {}
  48. 	~AssertsCounter() { std::cerr << Endl << "DIAG: " << (counter == 0 ? "OK" : "FAIL!!!") << " Asserts count: " << counter << Endl; }
  49. 	void Increment() { counter++; }
  50. 	uint32_t counter;
  51. };
  52. AssertsCounter g_assertsCounter;
  53. #define LOCAL_ASSERT(expr) { if (!(expr)) {std::cerr << "ASSERT FAILED (" << __LINE__ << "): '" << #expr << "'" << Endl; g_assertsCounter.Increment(); _CrtDbgBreak(); } }
  54. #define LOCAL_ASSERT_EQ(expr1, expr2) { if ((expr1) != (expr2)) {std::cerr << "ASSERT FAILED (" << __LINE__ << "): '" << #expr1 << "' == '" << #expr2 << "' (" << (expr1) << " vs " << (expr2) << "')" << Endl; g_assertsCounter.Increment(); _CrtDbgBreak(); } }
  55. #else
  56. volatile bool isLocalTestEnabled = 0;
  57. #define LOCAL_ASSERT(expr)
  58. #define LOCAL_ASSERT_EQ(expr1, expr2)
  59. #endif
  60.  
  61. bool g_isLocalPrintEnabled = (bool)(LOCAL_TEST);
  62. #define LOCAL_PRINT() if (!g_isLocalPrintEnabled) { } else std::cerr // << .. << ..
  63.  
  64. typedef std::string string8_t;
  65. typedef long double ld_t;
  66.  
  67. typedef std::vector<size_t> vector_size_t;
  68. typedef std::vector<uint8_t> vector_uint8_t;
  69. typedef std::vector<int32_t> vector_int32_t;
  70. typedef std::vector<uint32_t> vector_uint32_t;
  71. typedef std::vector<int64_t> vector_int64_t;
  72. typedef std::vector<uint64_t> vector_uint64_t;
  73. typedef std::vector<string8_t> vector_string8_t;
  74.  
  75. typedef std::vector<vector_size_t> vector_2d_size_t;
  76. typedef std::vector<vector_int32_t> vector_2d_int32_t;
  77. typedef std::vector<vector_uint32_t> vector_2d_uint32_t;
  78. typedef std::vector<vector_int64_t> vector_2d_int64_t;
  79. typedef std::vector<vector_uint64_t> vector_2d_uint64_t;
  80.  
  81. typedef std::set<size_t> set_size_t;
  82. typedef std::set<int32_t> set_int32_t;
  83. typedef std::set<uint32_t> set_uint32_t;
  84. typedef std::set<int64_t> set_int64_t;
  85. typedef std::set<uint64_t> set_uint64_t;
  86. typedef std::set<string8_t> set_string8_t;
  87.  
  88. typedef std::multiset<size_t> multiset_size_t;
  89. typedef std::multiset<string8_t> multiset_string8_t;
  90.  
  91. // Auxiliary functions definition
  92. //
  93. template<typename T> void UpdateMin(T& a, const T b) {a = std::min(a, b);}
  94. template<typename T> void UpdateMax(T& a, const T b) {a = std::max(a, b);}
  95.  
  96. const ld_t Pi = std::atan(1.0L) * 4.0L;
  97. static const ld_t Eps = 1.0e-09;
  98. template<typename T> bool IsEqual(const T a, const T b) { return std::abs(a - b) < Eps; }
  99. template<typename T> bool IsGreater(const T a, const T b) { return a > b + Eps; }
  100. template<typename T> bool IsLess(const T a, const T b) { return a + Eps < b; }
  101. template<typename T> bool IsGreaterEqual(const T a, const T b) { return !IsLess(a, b); }
  102. template<typename T> bool IsLessEqual(const T a, const T b) { return !IsGreater(a, b); }
  103.  
  104. template<typename T> string8_t ToStr(const T& val) { std::ostringstream ostr; ostr << val; return ostr.str(); }
  105. template<typename T> bool FromStr(const string8_t& str, T& val) {std::istringstream istr(str); istr >> val; return !!istr; }
  106. template<typename T> T FromStr(const string8_t& str) {T val = {}; std::istringstream istr(str); istr >> val; return val; }
  107.  
  108. template<typename ContainerType, typename ValueType> bool Contains(const ContainerType& c, const ValueType& v) { return c.find(v) != c.end(); }
  109.  
  110. uint64_t SafeAdd(uint64_t a, uint64_t b) { uint64_t M = std::numeric_limits<uint64_t>::max(); return a <= M - b ? a + b : M; }
  111. uint64_t SafeMul(uint64_t a, uint64_t b) { uint64_t M = std::numeric_limits<uint64_t>::max(); return a <= M / b ? a * b : M; }
  112.  
  113. template<typename T> std::istream& operator>>(std::istream& ist, std::vector<T>& data)
  114. {
  115. 	LOCAL_ASSERT(!!ist);
  116. 	for (size_t i = 0; i < data.size(); i++) { ist >> data[i]; }
  117. 	return ist;
  118. }
  119.  
  120. template<typename T> T Read(std::istream& ist)
  121. {
  122. 	LOCAL_ASSERT(!!ist);
  123. 	T val; ist >> val; return val;
  124. }
  125.  
  126. template<typename T> std::ostream& operator<<(std::ostream& ost, const std::vector<T>& data)
  127. {
  128. 	for (size_t i = 0; i < data.size(); i++) { if (i != 0) { ost << ' '; } ost << data[i]; }
  129. 	return ost;
  130. }
  131.  
  132. struct IInteractor {
  133.     // TODO: Declare interaction operations here
  134. 	virtual uint32_t GetSum(const uint32_t i, const uint32_t j) = 0;
  135. };
  136.  
  137. class OnlineJudgeInteractor : public IInteractor {
  138. 	std::istream& ist;
  139. 	std::ostream& ost;
  140. public:
  141. 	OnlineJudgeInteractor(std::istream& ist, std::ostream& ost): ist(ist), ost(ost) {
  142. 	}
  143.  
  144.     // TODO: Implement online judje interaction operations here
  145. 	virtual uint32_t GetSum(const uint32_t i, const uint32_t j) override {
  146. 		ost << "? " << (i + 1) << " " << (j + 1) << Endl;
  147.         uint32_t s;
  148.         ist >> s;
  149.         return s;
  150. 	}
  151. };
  152.  
  153. class LocalTestInteractor : public IInteractor {
  154. 	const vector_uint32_t values;
  155.     std::ostream* const interactorLog;
  156.  
  157. public:
  158. 	LocalTestInteractor(const vector_uint32_t& values, std::ostream* const interactorLog)
  159.         : values(values)
  160.         , interactorLog(interactorLog) {
  161.         if (interactorLog) {
  162.             // TODO: dump initial information in order to be capable to use it in OnlineJudgeInteractor
  163.             (*interactorLog) << values.size() << Endl;
  164.         }
  165. 	}
  166.  
  167. 	virtual uint32_t GetSum(const uint32_t i, const uint32_t j) override {
  168.         const uint32_t s = values[i] + values[j];
  169.         if (interactorLog) {
  170.             // TODO: dump answer information in order to be capable to use it in OnlineJudgeInteractor
  171.             (*interactorLog) << s << Endl;
  172.         }
  173.         return s;
  174. 	}
  175. };
  176.  
  177. class Solver {
  178. 	IInteractor& Interactor;
  179.  
  180. public:
  181. 	Solver(IInteractor& interactor): Interactor(interactor) {
  182. 	}
  183.  
  184.     vector_uint32_t GetAnswer(const size_t n) {
  185.         // TODO: insert solution implementation here
  186.         vector_uint32_t ans(n);
  187.  
  188.         const uint32_t s01 = Interactor.GetSum(0, 1);
  189.         const uint32_t s12 = Interactor.GetSum(1, 2);
  190.         const uint32_t s20 = Interactor.GetSum(2, 0);
  191.  
  192.         const uint32_t s012 = (s01 + s12 + s20) / 2;
  193.         ans[0] = s012 - s12;
  194.         ans[1] = s012 - s20;
  195.         ans[2] = s012 - s01;
  196.  
  197.         for (uint32_t i = 3; i < n; i++) {
  198.             const uint32_t s = Interactor.GetSum(i - 1, i);
  199.             ans[i] = s - ans[i - 1];
  200.         }
  201.  
  202.         return ans;
  203.     }
  204. };
  205.  
  206. bool Solve(std::istream& ist, std::ostream& ost, const bool multipleTestMode, const bool useLocalTestInteractor, std::ostream* const interactorLog)
  207. {
  208.     // TODO: read initial input information, if needed
  209.     size_t n;
  210. 	ist >> n;
  211.  
  212. 	if (multipleTestMode && !ist)
  213. 		return false;
  214.  
  215.     std::unique_ptr<IInteractor> interactor;
  216.  
  217.     if (useLocalTestInteractor) {
  218. 	    if (multipleTestMode && !ist)
  219. 		    return false;
  220.  
  221.         // TODO: read hidden information for interactor
  222.         vector_uint32_t a(n);
  223.         ist >> a;
  224.  
  225. 	    if (multipleTestMode && !ist)
  226. 		    return false;
  227.  
  228. 	    interactor.reset(new LocalTestInteractor(a, interactorLog));
  229.     } else {
  230.         interactor.reset(new OnlineJudgeInteractor(ist, ost));
  231.     }
  232.     LOCAL_ASSERT(interactor.get());
  233.  
  234. 	//
  235. 	LOCAL_PRINT() << Endl << "Next test" << Endl;
  236. 	Solver solver(*interactor);
  237. 	const vector_uint32_t ans = solver.GetAnswer(n);
  238.  
  239.     // TODO: output answer in a proper form
  240. 	ost << "! " << ans << Endl;
  241.  
  242. 	return multipleTestMode;
  243. }
  244.  
  245.  
  246. void RunSolve(std::istream& ist, std::ostream& ost, const bool useLocalTestInteractor, std::ostream* const interactorLog)
  247. {
  248. #if !defined(ONLINE_JUDGE)
  249.     const bool multipleTestMode = true;
  250. 	while(Solve(ist, ost, multipleTestMode, useLocalTestInteractor, interactorLog)) {};
  251. #else
  252.     Solve(ist, ost, false, false, nullptr);
  253. #endif
  254. }
  255.  
  256. int main(int argc, const char *argv[])
  257. {
  258.     bool useLocalTestInteractor = false;
  259.     if (argc >= 2) {
  260.         if (std::string(argv[1]) == "-t") {
  261.             useLocalTestInteractor = true;
  262.             LOCAL_PRINT() << "Using local interactor" << Endl;
  263.         }
  264.     }
  265.  
  266.     std::unique_ptr<std::ofstream> interactorLog;
  267.     if (useLocalTestInteractor && argc >= 3) {
  268.         const char* const logFileName = argv[2];
  269.         LOCAL_PRINT() << "Using file '" << logFileName << "' for interactor input log saving" << Endl;
  270.         interactorLog.reset(new std::ofstream(logFileName));
  271.     }
  272.  
  273. 	RunSolve(std::cin, std::cout, useLocalTestInteractor, interactorLog.get());
  274. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
5
10
7
5
6
10
3
21
23
22
stdout
copy 
? 1 2
? 2 3
? 3 1
? 3 4
? 4 5
! 4 6 1 5 5
https://ideone.com/iZgFrK
language:
C++14 (gcc 8.3)
created:
5 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!