Submission #1103260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103260		matthew	Mouse (info1cup19_mouse)	C++17	13 / 100	10 ms	592 KiB

mouse

#include <stdio.h>
#include <vector>
#include <set>
#include <stdlib.h>
#include "grader.h"
 
const int MAX_N = 1'000;
 
// candidates[i] = ce numere pot sa apara pe pozitia i
std::set<int> candidates[MAX_N];
int perm[MAX_N];
char vis[MAX_N];
 
int query(std::vector<int> guess);
 
void init_candidates(int n) {
  for(int i = 0; i < n; i++) {
    candidates[i].clear();
    for(int j = 0; j < n; j++) {
      candidates[i].insert(j);
    }
  }
}
 
int ask(int n) {
  std::vector<int> guess;
  for(int i = 0; i < n; i++) {
    guess.push_back(perm[i] + 1);
  }
  return query(guess);
}
 
int get_rand_from_set(std::set<int> s) {
  int size = s.size();
  int pos = rand() % size;
  auto it = s.begin();
  std::advance(it, pos);
  return *it;
}
 
/*
int n, qs;
std::vector<int> x;
*/
 
void find_permutation(int n) {
  for(int i = 0; i < n; i++) {
    while(candidates[i].size() > 1) {
      // completam pozitiile i..n-1
      perm[i] = get_rand_from_set(candidates[i]);
      for(int j = 0; j < n; j++) {
        vis[j] = 0;
      }
      for(int j = 0; j <= i; j++) {
        vis[perm[j]] = 1;
      }
      for(int j = i + 1; j < n; j++) {
        int remaining = n - j;
        int idx = 0;
        int r  = rand();
        int pos = r % remaining;
        for(int k = 0; k <= pos; k++) {
          while(idx < n && vis[idx]) {
            idx++;
          }
          if(k < pos) {
            idx++;
          }
        }
        perm[j] = idx;
        vis[idx] = 1;
      }
      int q = ask(n);
      if(q == i) {
        for(int j = i; j < n; j++) {
          candidates[j].erase(perm[j]);
        }
      }
    }
    perm[i] = *candidates[i].begin();
    for(int j = i + 1; j < n; j++) {
      candidates[j].erase(perm[i]);
    }
  }
}
 
void send_answer(int n) {
  std::vector<int> res;
  for(int i = 0; i < n; i++) {
    res.push_back(perm[i] + 1);
  }
  query(res);
}
 
void solve(int n) {
  init_candidates(n);
  find_permutation(n);
  send_answer(n);
}
 
/*
int main() {
  scanf("%d", &n);
 
  for(int i = 0; i < n; i++) {
    int a;
    scanf("%d", &a);
    x.push_back(a);
  }
 
  qs = 0;
  solve(n);
 
  return 0;
}
int query(std::vector<int> guess) {
  qs++;
  int cnt = 0;
  for(int i = 0; i < n; i++) {
    cnt += (guess[i] == x[i]);
  }
  printf("answer %d for query %d:\n", cnt, qs);
  for(int i = 0; i < n; i++) {
    printf("%d ", guess[i]);
  }
  printf("\n");
  return cnt;
}
*/

• Subtask 1: 13 / 13
• Subtask 2: 0 / 38
• Subtask 3: 0 / 49