Submission #607285

#	Time	Username	Problem	Language	Result	Execution time	Memory
607285		DanerZein	ICC (CEOI16_icc)	C++14	7 / 100	110 ms	848 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N=110;
int pa[MAX_N];
void init(int n){
  for(int i=0;i<=n;i++) pa[i]=i;
}
int findset(int x){
  if(pa[x]==x) return x;
  return pa[x]=findset(pa[x]);
}
bool issameset(int i,int j){
  return findset(i)==findset(j);
}
void unionset(int i,int j){
  if(!issameset(i,j)){
    int u=findset(i),v=findset(j);
    pa[u]=v;
  }
}
int c=0;
int myQuery(vector<int> y,vector<int> x){
  int t=y.size();
  int *qu1=new int[t];
  for(int i=0;i<t;i++)
    qu1[i]=y[i];
  
  t=x.size();
  int *qu2=new int[t];
  for(int i=0;i<t;i++)
    qu2[i]=x[i];
  c++;
  return query(y.size(),x.size(),qu1,qu2);
}
vector<int> firstHalf(vector<int> x){
  vector<int> f;
  for(int i=0;i<x.size()/2;i++) f.push_back(x[i]);
  return f;
}
vector<int> secondHalf(vector<int> x){
  vector<int> f;
  for(int i=x.size()/2;i<x.size();i++) f.push_back(x[i]);
  return f;
}
void divide(vector<int> y,vector<int> x){
  if(x.size()==1 && y.size()==1){
    //cout<<x[0]<<" "<<y[0]<<endl;
    setRoad(x[0],y[0]);
    unionset(x[0],y[0]);
    return;
  }
  vector<int> y1=firstHalf(y),y2=secondHalf(y);
  vector<int> x1=firstHalf(x),x2=secondHalf(x);
  if(myQuery(x1,y1)) divide(x1,y1);
  else if(myQuery(x1,y2)) divide(x1,y2);
  else if(myQuery(x2,y1)) divide(x2,y1);
  else divide(x2,y2);
}
int N;
vector<int> conjun(vector<int> x){
  vector<int> con;
  for(int i=0;i<x.size();i++){
    for(int j=1;j<=N;j++){
      if(issameset(x[i],j)) con.push_back(j);
    }
  }
  return con;
}
void divCon(vector<int> y,vector<int> x){
  vector<int> y1=firstHalf(y),y2=secondHalf(y);
  vector<int> x1=firstHalf(x),x2=secondHalf(x);
  if(x.size()==1 && y.size()==1){
    divide(conjun(x),conjun(y));
    return;
  }
  if(myQuery(conjun(x1),conjun(y1))) divCon(x1,y1);
  else if(myQuery(conjun(x2),conjun(y1))) divCon(x2,y1);
  else if(myQuery(conjun(x1),conjun(y2))) divCon(x1,y2);
  else divCon(x2,y2);
  
}
void findUnion(vector<int> con){
  int k=log2(con.size());
  for(int i=0;i<k;i++){
    vector<int> c1,c2;
    for(int j=0;j<con.size();j++){
      if(j&(1<<i)) c1.push_back(con[j]);
      else c2.push_back(con[j]);
    }
    if(myQuery(conjun(c1),conjun(c2))){
      divCon(c1,c2);
      return;
    }
  }
}
void run(int n){
  N=n;
  init(n);
  for(int k=0;k<n-1;k++){
    vector<int> con;
    for(int i=1;i<=n;i++) con.push_back(findset(i));
    sort(con.begin(),con.end());
    con.erase(unique(con.begin(),con.end()),con.end());
    findUnion(con);
  }
}

Compilation message (stderr)

icc.cpp: In function 'std::vector<int> firstHalf(std::vector<int>)':
icc.cpp:38:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for(int i=0;i<x.size()/2;i++) f.push_back(x[i]);
      |               ~^~~~~~~~~~~
icc.cpp: In function 'std::vector<int> secondHalf(std::vector<int>)':
icc.cpp:43:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int i=x.size()/2;i<x.size();i++) f.push_back(x[i]);
      |                        ~^~~~~~~~~
icc.cpp: In function 'std::vector<int> conjun(std::vector<int>)':
icc.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i=0;i<x.size();i++){
      |               ~^~~~~~~~~
icc.cpp: In function 'void findUnion(std::vector<int>)':
icc.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int j=0;j<con.size();j++){
      |                 ~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10