oj.uz

Submission #127599

# Submission time Handle Problem Language Result Execution time Memory
127599 2019-07-09T16:02:37 Z davitmarg ICC (CEOI16_icc) C++17
100 / 100
 189 ms 732 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
 
#ifndef death
 #include "icc.h"
#endif
 
using namespace std;
 
 
#ifdef death
 
int cnt=0;
 
bool query(int n,int m,int* a,int* b)
{
	cnt++;
	//return 0;
    cout<<"?\n";
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
	cout<<endl;
    for(int i=0;i<m;i++)
        cout<<b[i]<<" ";
	cout<<endl;
	int ans;
	cin>>ans;
    return ans;
}
 
void setRoad(int a,int b)
{
	cout<<"! "<<a<<" "<<b<<endl;
}
 
#endif
 
bool query(vector<int> a,vector<int> b)
{
    int A[102],B[102];
    for(int i=0;i<a.size();i++)
        A[i]=a[i];
    for(int i=0;i<b.size();i++)
        B[i]=b[i];
    return query((int)a.size(),(int)b.size(),A,B);
}
 
bool query(vector<vector<int>> A,vector<vector<int>> B)
{
    vector<int> a,b;
    for(int i=0;i<A.size();i++)
        while(!A[i].empty())
		{
            a.PB(A[i].back());
            A[i].pop_back();
		}
 
    for(int i=0;i<B.size();i++)
        while(!B[i].empty())
		{
            b.PB(B[i].back());
            B[i].pop_back();
		}
    if(a.empty() || b.empty())
		return 0;
 
    return query(a,b);
}
 
int n,p[102];
vector<vector<int>> s,t;
vector<int> r;
 
void dsu(int a,int b)
{
    if(s[a].size()<s[b].size())
		swap(a,b);
    vector<int> A,B;
    A=s[a];
	B=s[b];
    while(!s[b].empty())
	{
		p[s[b].back()]=p[s[a][0]];
		s[a].PB(s[b].back());
        s[b].pop_back();
	}
}
 
void get(vector<vector<int>> A,vector<vector<int>> B)
{
    vector<int> a,b;
    int x,y;
    for(int i=0;i<A.size();i++)
        while(!A[i].empty())
		{
            a.PB(A[i].back());
            A[i].pop_back();
		}
 
    for(int i=0;i<B.size();i++)
        while(!B[i].empty())
		{
            b.PB(B[i].back());
            B[i].pop_back();
		}
    random_shuffle(all(a));
    random_shuffle(all(b));
    int l,r,m;
    x=a.back();
    y=b.back();
    l=0;
    r=a.size()-2;
    while(l<=r)
	{
		m=(l+r)/2;
		vector<int> p;
        for(int i=0;i<=m;i++)
			p.PB(a[i]);
        if(query(p,b)==1)
		{
            x=a[m];
			r=m-1;
		}
		else
            l=m+1;
	}
 
 
    l=0;
    r=b.size()-2;
    while(l<=r)
	{
		m=(l+r)/2;
		vector<int> p;
        for(int i=0;i<=m;i++)
			p.PB(b[i]);
        if(query(p,vector<int>(1,x))==1)
		{
            y=b[m];
			r=m-1;
		}
		else
            l=m+1;
	}
 
    setRoad(x,y);
    dsu(p[x],p[y]);
}
 
void solve(int k)
{
    vector<vector<int>> c[2];
    for(int i=1;i<t.size();i++)
        c[(i/k)%2].PB(t[i]);
    if(k==1 || query(c[0],c[1]))
        get(c[0],c[1]);
	else
		return solve(k/2);
}
 
void run(int N)
{
	n=N;
	s.PB(vector<int>(0));
	r.PB(0);
 
    for(int i=1;i<=n;i++)
	{
		s.PB(vector<int>(0));
		r.PB(i);
        s[i].PB(i);
        p[i]=i;
	}
 
    N--;
    N--;
    srand(6848654);
    while(N>0)
	{
		t.resize(1,vector<int>(0));
		for(int i=0;i<s.size();i++)
			if(!s[i].empty())
				t.PB(s[i]);
		int K=0;
		while((1<<K)<(t.size()-1))
			K++;
		K=(1<<K);
		solve(K/2);
	}
 
 
    for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
            if(!s[i].empty() && !s[j].empty())
			{
				get(vector<vector<int>>(1,s[i]),vector<vector<int>>(1,s[j]));
                break;
			}
}
 
 
#ifdef death
 
int main()
{
	int N;
	cin>>N;
    run(N);
    cout<<"!! "<<cnt<<" !!"<<endl;
	return 0;
}
 
#endif
 
 
/*
 
 
 
 
*/

Compilation message

icc.cpp: In function 'bool query(std::vector<int>, std::vector<int>)':
icc.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<a.size();i++)
                 ~^~~~~~~~~
icc.cpp:63:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<b.size();i++)
                 ~^~~~~~~~~
icc.cpp: In function 'bool query(std::vector<std::vector<int> >, std::vector<std::vector<int> >)':
icc.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<A.size();i++)
                 ~^~~~~~~~~
icc.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<B.size();i++)
                 ~^~~~~~~~~
icc.cpp: In function 'void get(std::vector<std::vector<int> >, std::vector<std::vector<int> >)':
icc.cpp:113:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<A.size();i++)
                 ~^~~~~~~~~
icc.cpp:120:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<B.size();i++)
                 ~^~~~~~~~~
icc.cpp: In function 'void solve(int)':
icc.cpp:173:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<t.size();i++)
                 ~^~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:201:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<s.size();i++)
               ~^~~~~~~~~
icc.cpp:205:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while((1<<K)<(t.size()-1))
         ~~~~~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Ok! 103 queries used.
2 Correct 9 ms 508 KB Ok! 104 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 580 KB Ok! 568 queries used.
2 Correct 51 ms 504 KB Ok! 654 queries used.
3 Correct 50 ms 504 KB Ok! 638 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 640 KB Ok! 1454 queries used.
2 Correct 167 ms 632 KB Ok! 1617 queries used.
3 Correct 148 ms 632 KB Ok! 1502 queries used.
4 Correct 156 ms 504 KB Ok! 1546 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 504 KB Ok! 1448 queries used.
2 Correct 149 ms 656 KB Ok! 1482 queries used.
3 Correct 189 ms 632 KB Ok! 1597 queries used.
4 Correct 145 ms 616 KB Ok! 1469 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 616 KB Ok! 1587 queries used.
2 Correct 171 ms 732 KB Ok! 1598 queries used.
3 Correct 163 ms 632 KB Ok! 1599 queries used.
4 Correct 158 ms 632 KB Ok! 1554 queries used.
5 Correct 156 ms 632 KB Ok! 1538 queries used.
6 Correct 163 ms 632 KB Ok! 1600 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 732 KB Ok! 1588 queries used.
2 Correct 163 ms 632 KB Ok! 1610 queries used.