Submission #700978

#TimeUsernameProblemLanguageResultExecution timeMemory
700978beaconmcICC (CEOI16_icc)C++14
100 / 100
149 ms596 KiB
#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 (stderr)

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]];
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...