Submission #150333

#	Time	Username	Problem	Language	Result	Execution time	Memory
150333		1 WA = 5 Push Up (#200)	Lokahian Relics (FXCUP4_lokahia)	C++17	0 / 100	7 ms	688 KiB

lokahia

#include "lokahia.h"
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
int p[706];
int query[706][3];

int find(int a){
  if(p[a] < 0) return a;
  return p[a] = find(p[a]);
}
int uni(int a, int b){
  a = find(a);
  b = find(b);
  if(a==b) return 0;
  p[a] += p[b];
  p[b] = a;
  return -p[a];
}

int FindBase(int N){
  srand(234316);
  int GROUP_IDX = N+1;
  if(N==1) return 0;
  for(int i = 0; i < 700; i++){
    p[i] = -1;
  }
  int GUESS_IDX = 0;
  while(GUESS_IDX < 600){
    int a = 0, b = 0;
    while(find(a) == find(b)){
      a = rand()%N;
      b = rand()%N;
      //printf("%d %d %d %d\n",a,b,find(a),find(b));
    }
    int ret = CollectRelics(a,b);
    //printf("%d %d %d\n",a,b,ret);
    query[GUESS_IDX][0]=a;
    query[GUESS_IDX][1]=b;
    query[GUESS_IDX][2]=ret;
    if(ret != -1){
      int sz = uni(a, b);
      if(sz > N/2){
        int ret = -1;
        for(int i = 0; i < GUESS_IDX; i++){
          if(find(query[GUESS_IDX][0]) != find(a) or find(query[GUESS_IDX][1]) != find(a)) continue;
          ret = max(ret, query[GUESS_IDX][1]);         
        }
        return ret;
      }
    }
    GUESS_IDX++;
  }
	for(int t = 0; t < N; t++){
    if(-p[t] > N/2){
      int ret = -1;
        for(int i = 0; i < GUESS_IDX; i++){
          if(find(query[GUESS_IDX][0]) != find(t) or find(query[GUESS_IDX][1]) != find(t)) continue;
          ret = max(ret, query[GUESS_IDX][1]);         
        }
      return ret;
    }
  }
  return -1;
}

Compilation message (stderr)

lokahia.cpp: In function 'int FindBase(int)':
lokahia.cpp:24:7: warning: unused variable 'GROUP_IDX' [-Wunused-variable]
   int GROUP_IDX = N+1;
       ^~~~~~~~~

• Subtask 1: 0 / 100