API tools faq
paste
Advertisement
Dynonychus

EGOI TSTs 2025 - Day 1 - Question 3 - Find An Element

Dynonychus
Jun 25th, 2025 (edited)
518
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.23 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //Do not change anything here. Go to line 42 to find the Participant class.
  5.  
  6. int grader_N, grader_queries_used = 0;
  7. vector<int> grader_S;
  8.  
  9. void grader_wa(string S) {
  10.     cerr << S << '\n';
  11.     cout << "fail" << '\n';
  12.     exit(0);
  13. }
  14.  
  15. int query(vector<int> X) {
  16.     grader_queries_used++;
  17.  
  18.     if (grader_queries_used > 50)
  19.         grader_wa("More than 50 queries used.");
  20.  
  21.     if ((int)X.size() != grader_N){
  22.         grader_wa("Size of provided vector does not match for query");
  23.     }
  24.     for (int x : X){
  25.         if (!(0 <= x && x <= 1)){
  26.             grader_wa("Elements other than 0 or 1 found in vector for query");
  27.         }
  28.     }
  29.    
  30.     int intersection = 0;
  31.     for (int i = 0; i < grader_N; i++){
  32.         if (X[i] == 1 && grader_S[i] == 1){
  33.             intersection++;
  34.         }
  35.     }
  36.     intersection %= 2;
  37.     return intersection;
  38. }
  39.  
  40.  
  41.  
  42. struct Participant
  43. {
  44. //DO NOT CHANGE ANYTHING ABOVE THIS LINE!
  45. //You may create variables and functions here.
  46.  
  47.     int solve(int N)
  48.     {
  49.         // For demonstration purposes only
  50.  
  51.         // vector <int> A(N, 0);
  52.         // A[0] = 1;
  53.         // int queryResult = query(A);
  54.  
  55.         int a=0;
  56.         int i=0;
  57.  
  58.         int mn = 0;
  59.  
  60.         mn = (1 << 14);
  61.        
  62.         vector<int> vec(N);
  63.  
  64.         while(true) {
  65.             for(i=0;i<N;i++) {
  66.                 a = rand()%2;
  67.  
  68.                 vec[i] = a;
  69.             }
  70.  
  71.             a=0;
  72.  
  73.             a = query(vec);
  74.  
  75.             if(a)
  76.             break;
  77.         }
  78.        
  79.         vector<int> veco;
  80.  
  81.         while(true) {
  82.             veco.clear();
  83.            
  84.             int b=0;
  85.  
  86.             for(i=0;i<N;i++) {
  87.                 if(vec[i] == 1)
  88.                 b++;
  89.             }
  90.  
  91.             a=0;
  92.  
  93.             for(i=0;i<N;i++) {
  94.                 if(vec[i] == 0)
  95.                 veco.push_back(0);
  96.  
  97.                 else if(a < (b/2)) {
  98.                     veco.push_back(1);
  99.                     a++;
  100.                 }
  101.  
  102.                 else
  103.                 veco.push_back(0);
  104.             }
  105.  
  106.             a = 0;
  107.            
  108.             a = query(veco);
  109.  
  110.             if(a) {
  111.                 vec = veco;
  112.             }
  113.  
  114.             else {
  115.                 veco.clear();
  116.  
  117.                 for(i=0;i < N;i++) {
  118.                     if(a >= (b/2))
  119.                     break;
  120.  
  121.                     if(vec[i] == 1) {
  122.                         vec[i] = 0;
  123.                         a++;
  124.                     }
  125.                 }
  126.             }
  127.  
  128.             a=0;
  129.  
  130.             for(i=0;i<N;i++) {
  131.                 if(vec[i] == 1)
  132.                 a++;
  133.             }
  134.  
  135.             if(a == 1)
  136.             break;
  137.         }
  138.  
  139.         for(i=0;i < N;i++) {
  140.             if(vec[i] == 1)
  141.             return i;
  142.         }
  143.  
  144.         // return 0;
  145.     }
  146.  
  147. //DO NOT CHANGE ANYTHING BELOW THIS LINE!
  148. };
  149.  
  150.  
  151.  
  152. int main() {
  153.     cin >> grader_N;
  154.  
  155.     grader_S = vector<int>(grader_N);
  156.     for(int i = 0; i < grader_N; i++){
  157.         int x; cin >> x;
  158.         grader_S[i] = x;
  159.     }
  160.  
  161.     grader_queries_used = 0;
  162.  
  163.     Participant pa;
  164.  
  165.     int result = pa.solve(grader_N);
  166.  
  167.     cerr << "Returned value = " << result << "\n";
  168.     if (!(0 <= result && result < grader_N)){
  169.         grader_wa("Returned value out of bounds");
  170.     }
  171.  
  172.     if (grader_S[result] == 0){
  173.         grader_wa("Returned value not in set");
  174.     }
  175.  
  176.     cout << "pass\n";
  177. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!