| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 148274 |
2019-08-31T19:35:58 Z |
12tqian |
ICC (CEOI16_icc) |
C++14 |
|
151 ms |
744 KB |
#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include "icc.h"
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const double PI = 4 * atan(1);
#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>
#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
#define trav(a, x) for (auto& a : x)
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
void fast_io(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
}
void io(string taskname){
string fin = taskname + ".in";
string fout = taskname + ".out";
const char* FIN = fin.c_str();
const char* FOUT = fout.c_str();
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
fast_io();
}
template<int SZ> struct DSU{
int par[SZ], sz[SZ];
DSU(){
for(int i = 0; i<SZ; i++){
par[i] = i;
sz[i] = 1;
}
}
int get(int x){
if(par[x] != x){
par[x] = get(par[x]);
}
return par[x];
}
bool unite(int x, int y){
x = get(x);
y = get(y);
if(x == y){
return false;
}
if(sz[x] < sz[y]){
swap(x, y);
}
sz[x] += sz[y];
par[y] = x;
return true;
}
};
const int MAX = 1e2 + 5;
DSU<MAX> t;
int n;
vector<vi> groups;
///grader
/*
void setRoad(int i, int j){
cout << "Set Road: " << i << " " << j << endl;
return;
}
bool query(int sz_a, int sz_b, vi a, vi b){
cout << a << " " << b << endl;
int res;
cin >> res;
return res;
}*/
void answer(int i, int j){
setRoad(i+1, j+1);
t.unite(i, j);
}
int arr1[MAX], arr2[MAX];
bool ask(vi& a, vi& b){
f0r(i, sz(a)) arr1[i] = a[i] + 1;
f0r(i, sz(b)) arr2[i] = b[i] + 1;
return query(sz(a), sz(b), arr1, arr2);
/*vi v1;
vi v2;
for(int x: a) v1.eb(x+1);
for(int x: b) v2.eb(x+1);
return query(sz(a), sz(b), v1, v2);*/
}
pii connect(vi& a, vi& b){
int lo = 0;
int hi = sz(b) - 1;
while(lo != hi){
int mid = (lo + hi)/2;
vi c;
f1r(i,lo, mid+1) c.eb(b[i]);
int val = ask(a, c);
//cout << val << endl;
if(val){
hi = mid;
}
else{
lo = mid+1;
}
}
// cout << "done" << endl;
vi c;
c.eb(b[lo]);
lo = 0;
hi = sz(a) - 1;
while(lo != hi){
int mid = (lo + hi)/2;
vi d;
f1r(i, lo, mid+1) d.eb(a[i]);
int val = ask(d, c);
//cout << val << endl;
if(val){
hi = mid;
}
else{
lo = mid + 1;
}
}
return mp(c[0], a[lo]);
}
vi convert(vi& a, vector<vi>& v){
vi res;
for(auto i: a){
for(int j: v[i]) res.eb(j);
}
return res;
}
pii solve(vector<vi>& v){
vector<vi> cur;
vector<vi> nxt;
vi tmp;
f0r(i, sz(v)) tmp.eb(i);
cur.eb(tmp);
while(true){
vi a;
vi b;
for(auto x: cur){
f0r(i, sz(x)/2) a.eb(x[i]);
f1r(i, sz(x)/2, sz(x)) b.eb(x[i]);
}
vi c = convert(a, v);
vi d = convert(b, v);
if(ask(c, d)){
return connect(c, d);
}
else{
nxt.clear();
for(auto x: cur){
vi tmp1;
vi tmp2;
if(sz(x)/2>1) f0r(i, sz(x)/2) tmp1.eb(x[i]);
if(sz(x) -sz(x)/2 >1) f1r(i, sz(x)/2, sz(x)) tmp2.eb(x[i]);
if(sz(tmp1)>0) nxt.eb(tmp1);
if(sz(tmp2)>0) nxt.eb(tmp2);
}
cur.clear();
for(auto x: nxt) cur.eb(x);
}
}
}
void run(int N){
n = N;
f0r(i, n){
vi tmp;
tmp.eb(i);
groups.eb(tmp);
}
f0r(i, n-1){
pii res = solve(groups);
answer(res.f, res.s);
set<int> vals;
map<int, int> m;
f0r(j, n){
vals.insert(t.get(j));
}
int cnt = 0;
for(auto x: vals){
m[x] = cnt;
cnt++;
}
groups.clear();
f0r(j, sz(m)){
vi tmp;
groups.eb(tmp);
}
f0r(j, n){
groups[m[t.get(j)]].eb(j);
}
}
}
/*
int main(){
fast_io();
int N;
cin >> N;
run(N);
return 0;
}
*/
Compilation message
icc.cpp:1:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/stack:200000000")
icc.cpp: In function 'void io(std::__cxx11::string)':
icc.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(FIN, "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~
icc.cpp:54:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(FOUT, "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
632 KB |
Ok! 105 queries used. |
| 2 |
Correct |
9 ms |
636 KB |
Ok! 100 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
504 KB |
Ok! 517 queries used. |
| 2 |
Correct |
46 ms |
632 KB |
Ok! 577 queries used. |
| 3 |
Correct |
45 ms |
632 KB |
Ok! 569 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
744 KB |
Ok! 1427 queries used. |
| 2 |
Correct |
147 ms |
584 KB |
Ok! 1420 queries used. |
| 3 |
Correct |
151 ms |
604 KB |
Ok! 1558 queries used. |
| 4 |
Correct |
142 ms |
576 KB |
Ok! 1470 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
144 ms |
580 KB |
Ok! 1477 queries used. |
| 2 |
Correct |
143 ms |
504 KB |
Ok! 1449 queries used. |
| 3 |
Correct |
146 ms |
504 KB |
Ok! 1444 queries used. |
| 4 |
Correct |
143 ms |
632 KB |
Ok! 1488 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
147 ms |
632 KB |
Ok! 1433 queries used. |
| 2 |
Correct |
147 ms |
580 KB |
Ok! 1425 queries used. |
| 3 |
Correct |
148 ms |
580 KB |
Ok! 1461 queries used. |
| 4 |
Correct |
149 ms |
592 KB |
Ok! 1529 queries used. |
| 5 |
Correct |
143 ms |
588 KB |
Ok! 1485 queries used. |
| 6 |
Correct |
150 ms |
588 KB |
Ok! 1544 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
147 ms |
576 KB |
Ok! 1449 queries used. |
| 2 |
Correct |
148 ms |
580 KB |
Ok! 1420 queries used. |
