oj.uz

Submission #1118140

# Submission time Handle Problem Language Result Execution time Memory
1118140 2024-11-25T03:38:33 Z kokoxuya Carnival (CEOI14_carnival) C++14
100 / 100
 38 ms 592 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define ss second
#define ff first
#define piii pair<int,pii>
#define debu(x) (cerr << #x  << " = "<< x << "\n")
#define debu2(x,y) (cerr << #x  << " = "<< x << " " << #y << " = " << y << "\n")
#define debu3(x,y,z) (cerr << #x  << " = "<< x << " " << #y << " = " << y << " " << #z << " = " << z<< "\n")
#define bitout(x,y) {\
	cerr << #x << " : ";\
	for (int justforbits = y; justforbits >=0; justforbits--)cout << (((1 << justforbits) & x)>=1);\
	cout << "\n";\
}
#define rangeout(j,rangestart,rangeend) {\
	cerr << "outputting" << #j<< ":\n";\
	for (int forrang = rangestart; forrang <= rangeend; forrang++)cerr << j[forrang] << " ";\
}
#define c1 cerr << "Checkpoint 1! \n\n"
#define c2 cerr << "Checkpoint 2! \n\n"
#define c3 cerr << "Checkpoint 3! \n\n"
#define c4 cerr << "Checkpoint 4! \n\n"
#define defN 151
#define rn0(a,x) for (int x = 0; x < a; x++);
#define rn1(a,x) for (int x = 0; x < a; x++);

//0 and 1-index mixup
vector<int>corr = {0,1,1,3};
int n;

int outp(int type, vector<int>& tbo)
{
	cout << type << " ";
	for (int x : tbo)cout << x << " ";
	cout << endl;
	
	if (type == 0)exit(0);
	int n;
	cin >> n;
	return n;
	
	/*if (!type)
	{
		for (int a = 0; a < n; a++)
		{
			for (int b = 0; b < n; b++)
			{
				if (corr[a] == corr[b])
				{
					if (tbo[a] == tbo[b])continue;
					debu2(a,b);
					debu2(tbo[a],tbo[b]);
					debu2(corr[a],corr[b]);
					cout << "Failed :(\n";
					exit (0);
				}
				else if (corr[a] != corr[b])
				{
					if (tbo[a] != tbo[b])continue;
					debu(a);
					cout << "Failed :(\n";
					exit (0);
				}
			}
		}
		cout << "Passed! :)\n";
		exit (0);
	}
	else
	{
		vector<bool>pres(n+1,false);
		int ret = 0;
		for (int x : tbo)
		{
			x--;
			if (!pres[corr[x]])ret++;
			pres[corr[x]] = true;
		}
		debu(ret);
		return ret;
	}*/
}



vector<int>pointers(defN);

bool checkers(int star, int en, int x)
{
	int t1,t2;
	vector<int>xx;

	for (int a = star; a <= en; a++)
	{
		xx.pb(a);
	}
	
	t1 = outp(xx.size(),xx);
	xx.pb(x);
	t2 = outp(xx.size(),xx);
	
	return (t1 == t2);
}

int leader(int x)
{
	if (pointers[x] == x)return x;
	pointers[x] = leader(pointers[x]);
	return pointers[x];
}

void merge(int x,int y)
{
	debu2(x,y);
	pointers[leader(x)] = leader(y);
}

signed main()
{
    int t1,t2,t3,t4;
    
	cin >> n;
	
	for (int a=1;a<=n;a++) pointers[a] = a;
	
	for (int a = 2; a <=n;a++)
	{
		if (!checkers(1,a-1,a))continue;
		int hi = a-1, lo = 1,mid;

		int ash = -1;
		while (hi >= lo)
		{
			mid = (hi+lo)/2;
			if (checkers(lo,mid,a))
			{
				ash = mid;
				hi = mid - 1;
			}
			else
			{
				lo = mid + 1;
			}
		}
		
		merge(a,ash);
	}
	
	int currat = 1;
	vector<int>ans(n+1,-1);	
	for (int a = 1; a <= n; a++){ans[a] = ((leader(a)==a)?(currat++):ans[leader(a)]);/*debu2(a,ans[a]);*/}
	//for (int a = 1; a <= n; a++)cout << pointers[a] << " ";cout<<"\n";
	
	ans.erase(ans.begin());
	outp(0,ans);
}

//1. for each one: check if same as any previous ones!
//2. to check: binary search : from 1 to a-1, inclusive
//3. initial check to see if there are any that are similar
//4. including lo and hi: go half, until reach
//5. if the same, merge the larger to the smaller
//6. assign a number to each one, and same number as leader if in a non-self headed group

Compilation message

carnival.cpp: In function 'int main()':
carnival.cpp:123:9: warning: unused variable 't1' [-Wunused-variable]
  123 |     int t1,t2,t3,t4;
      |         ^~
carnival.cpp:123:12: warning: unused variable 't2' [-Wunused-variable]
  123 |     int t1,t2,t3,t4;
      |            ^~
carnival.cpp:123:15: warning: unused variable 't3' [-Wunused-variable]
  123 |     int t1,t2,t3,t4;
      |               ^~
carnival.cpp:123:18: warning: unused variable 't4' [-Wunused-variable]
  123 |     int t1,t2,t3,t4;
      |                  ^~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 336 KB Output is correct
2 Correct 29 ms 592 KB Output is correct
3 Correct 14 ms 336 KB Output is correct
4 Correct 7 ms 336 KB Output is correct
5 Correct 35 ms 336 KB Output is correct
6 Correct 31 ms 452 KB Output is correct
7 Correct 25 ms 336 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 336 KB Output is correct
2 Correct 34 ms 336 KB Output is correct
3 Correct 12 ms 336 KB Output is correct
4 Correct 10 ms 592 KB Output is correct
5 Correct 28 ms 336 KB Output is correct
6 Correct 30 ms 336 KB Output is correct
7 Correct 35 ms 592 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 592 KB Output is correct
2 Correct 35 ms 516 KB Output is correct
3 Correct 26 ms 444 KB Output is correct
4 Correct 8 ms 444 KB Output is correct
5 Correct 26 ms 504 KB Output is correct
6 Correct 31 ms 336 KB Output is correct
7 Correct 29 ms 336 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 448 KB Output is correct
2 Correct 37 ms 448 KB Output is correct
3 Correct 14 ms 336 KB Output is correct
4 Correct 8 ms 448 KB Output is correct
5 Correct 27 ms 592 KB Output is correct
6 Correct 24 ms 336 KB Output is correct
7 Correct 33 ms 452 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 592 KB Output is correct
2 Correct 38 ms 336 KB Output is correct
3 Correct 19 ms 336 KB Output is correct
4 Correct 20 ms 336 KB Output is correct
5 Correct 23 ms 592 KB Output is correct
6 Correct 15 ms 452 KB Output is correct
7 Correct 9 ms 448 KB Output is correct