oj.uz

Submission #700978

# Submission time Handle Problem Language Result Execution time Memory
700978 2023-02-19T14:36:52 Z beaconmc ICC (CEOI16_icc) C++14
100 / 100
 149 ms 596 KB 
#include "icc.h"
#include <bits/stdc++.h>


typedef int ll;
using namespace std;


#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)


ll a_imp, b_imp;


ll n = 0;

ll cc[200];
int find(ll a){
  while (cc[a] != a){
    cc[a] = cc[cc[a]];
    a = cc[a];
  }
  return a;
}

// bool query(ll a, ll b, vector<ll> aa, vector<ll> bb){

//  bool left = 0, right = 0;
//  bool ll=0, rr = 0;
//  for (auto&i : aa) if (i==a_imp) left = 1;
//  for (auto&i : bb) if (i==b_imp) right = 1;

//  for (auto&i : aa) if (i==b_imp) ll = 1;
//  for (auto&i : bb) if (i==a_imp) rr = 1;



//  return (left&right) | (ll & rr);
// }


void unite(ll a, ll b){
  cc[find(a)] = find(b);
}

bool unpackquery(vector<ll> a, vector<ll> b){
  if (a.size() == 0 || b.size() == 0) return 0;
  vector<vector<ll>> unpacked(n+1);
  FOR(i,1,n+1) unpacked[find(i)].push_back(i);

  vector<ll> aa, bb;
  for (auto&i : a){
    for (auto&k : unpacked[i]){
      aa.push_back(k);
    }
  }
  for (auto&i : b){
    for (auto&k : unpacked[i]){
      bb.push_back(k);
    }
  }
  return query(aa.size(), bb.size(), aa.data(), bb.data());
}
bool realquery(vector<ll> a, vector<ll> b){
  if (a.size() == 0 || b.size() == 0) return 0;

  return query(a.size(), b.size(), a.data(), b.data());
}

void uniquesolve(vector<ll> a, vector<ll> b){
  ll xored = 0;

  FOR(i,0,ceil(log2(a.size()))){
    vector<ll> one;
    FOR(j,0,a.size()){
      if ((j & (1<<i))) one.push_back(a[j]);
    }

    if (realquery(one, b)){
      xored |= (1<<i);
    }

  }
  a = {a[xored]};
  swap(a,b);
  xored = 0;

  FOR(i,0,ceil(log2(a.size()))){
    vector<ll> one;
    FOR(j,0,a.size()){
      if ((j & (1<<i))) one.push_back(a[j]);
    }

    if (realquery(one, b)){
      xored |= (1<<i);
    }

  }
  a = {a[xored]};
  //cout << a[0] << " " << b[0] << endl;
  setRoad(a[0], b[0]);
  unite(a[0], b[0]);


}

void solve(vector<ll> a){
  vector<vector<ll>> unpacked(n+1);
  FOR(i,1,n+1) unpacked[find(i)].push_back(i);

  set<ll> idk;
  for (auto&i : a) idk.insert(find(i));

  a.clear();
    for (auto&i : idk) a.push_back(i);
  ll xored = 0;


  FOR(i,0,ceil(log2(a.size()))){
    vector<ll> one;
    vector<ll> zero;
    FOR(j,0,a.size()){
      if ((j & (1<<i)) != 0) one.push_back(a[j]);
      else zero.push_back(a[j]);
    }

    xored |= (1<<i) * unpackquery(one, zero);
  }
  //cout << xored << endl;

  ll xor2 = 0;

  FOR(i,0,ceil(log2(a.size()))){
    vector<ll> one;
    vector<ll> anti;

    FOR(j,0,a.size()){
      if ((xored ^ j) >= a.size() || j < (xored^j)) continue;
      if ((xored ^ j) == j) continue;
      if ((j & (1<<i)) != 0) one.push_back(j);
    }
    for (auto&j : one){
      if ((xored ^ j) >= a.size() || j < (xored^j)) continue;
      if ((xored ^ j) == j) continue;
      anti.push_back(xored ^ j);
    }

    FOR(j,0,one.size()) one[j] = a[one[j]];
    FOR(j,0,anti.size()) anti[j] = a[anti[j]];


    xor2 |= (1<<i) * unpackquery(one, anti);

  }
  vector<ll> news1, news2;
  //cout << a[xor2] << " " << a[xored^xor2] << endl;

  for (auto&i : unpacked[find(a[xor2])]){
    //cout << i << " ";
    news1.push_back(i);
  }
  for (auto&i : unpacked[find(a[xored^xor2])]){
    //cout << i <<" ";
    news2.push_back(i);
  }
  //cout << "SUS" << endl;
  //cout << news.size() << endl;
  uniquesolve(news1, news2);
}



void run(int N){
  n = N;
  FOR(i,0,200) cc[i] = i;
  vector<ll> sus(n);
  FOR(i,0,n) sus[i] = i+1;
  FOR(i,0,n-1){
    solve(sus);
  }
}

Compilation message

icc.cpp: In function 'void uniquesolve(std::vector<int>, std::vector<int>)':
icc.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
   77 |     FOR(j,0,a.size()){
      |         ~~~~~~~~~~~~               
icc.cpp:77:5: note: in expansion of macro 'FOR'
   77 |     FOR(j,0,a.size()){
      |     ^~~
icc.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
   92 |     FOR(j,0,a.size()){
      |         ~~~~~~~~~~~~               
icc.cpp:92:5: note: in expansion of macro 'FOR'
   92 |     FOR(j,0,a.size()){
      |     ^~~
icc.cpp: In function 'void solve(std::vector<int>)':
icc.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
  124 |     FOR(j,0,a.size()){
      |         ~~~~~~~~~~~~               
icc.cpp:124:5: note: in expansion of macro 'FOR'
  124 |     FOR(j,0,a.size()){
      |     ^~~
icc.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
  139 |     FOR(j,0,a.size()){
      |         ~~~~~~~~~~~~               
icc.cpp:139:5: note: in expansion of macro 'FOR'
  139 |     FOR(j,0,a.size()){
      |     ^~~
icc.cpp:140:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |       if ((xored ^ j) >= a.size() || j < (xored^j)) continue;
      |           ~~~~~~~~~~~~^~~~~~~~~~~
icc.cpp:145:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |       if ((xored ^ j) >= a.size() || j < (xored^j)) continue;
      |           ~~~~~~~~~~~~^~~~~~~~~~~
icc.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
  150 |     FOR(j,0,one.size()) one[j] = a[one[j]];
      |         ~~~~~~~~~~~~~~             
icc.cpp:150:5: note: in expansion of macro 'FOR'
  150 |     FOR(j,0,one.size()) one[j] = a[one[j]];
      |     ^~~
icc.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
  151 |     FOR(j,0,anti.size()) anti[j] = a[anti[j]];
      |         ~~~~~~~~~~~~~~~            
icc.cpp:151:5: note: in expansion of macro 'FOR'
  151 |     FOR(j,0,anti.size()) anti[j] = a[anti[j]];
      |     ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 492 KB Ok! 128 queries used.
2 Correct 6 ms 596 KB Ok! 123 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 468 KB Ok! 674 queries used.
2 Correct 30 ms 468 KB Ok! 536 queries used.
3 Correct 32 ms 484 KB Ok! 556 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 500 KB Ok! 1676 queries used.
2 Correct 99 ms 500 KB Ok! 1244 queries used.
3 Correct 117 ms 492 KB Ok! 1623 queries used.
4 Correct 121 ms 508 KB Ok! 1637 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 508 KB Ok! 1590 queries used.
2 Correct 149 ms 508 KB Ok! 1583 queries used.
3 Correct 107 ms 512 KB Ok! 1425 queries used.
4 Correct 138 ms 496 KB Ok! 1632 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 540 KB Ok! 1433 queries used.
2 Correct 113 ms 492 KB Ok! 1413 queries used.
3 Correct 108 ms 512 KB Ok! 1352 queries used.
4 Correct 115 ms 508 KB Ok! 1500 queries used.
5 Correct 131 ms 468 KB Ok! 1657 queries used.
6 Correct 134 ms 508 KB Ok! 1509 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 512 KB Ok! 1574 queries used.
2 Correct 117 ms 496 KB Ok! 1271 queries used.