Submission #1240217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240217		santi3223	Soccer Stadium (IOI23_soccer)	C++20	14 / 100	196 ms	31772 KiB

soccer

#include <bits/stdc++.h>
//#include "soccer.h"
using namespace std;
#define ll long long
#define vb vector<bool>
#define pb push_back
#define ff(aa, bb, cc) for(ll aa = bb; aa < cc; aa++)
#define vl vector<ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define ed "\n"
#define all(aaa) aaa.begin(), aaa.end()
#define rall(aaa) aaa.rbegin(), aaa.rend()
ll MOD = 1e9+7;

set<vl> st;
map<vl, ll> mp;
ll x = 0;
vl pre = {9, 8, 7, 7, 7, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 4, 4, 5, 5, 4, 4, 4, 4, 5, 5, 4, 4, 5, 4, 3, 3, 3, 3, 3, 3, 6, 6, 5, 5, 4, 4, 3, 3, 3, 3, 3, 3, 4, 3, 3, 4, 3, 3, 4, 3, 3, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 3, 2, 1, 1, 1, 1, 1, 1, 5, 4, 3, 1, 1, 1, 3, 2, 1, 1, 1, 0};


void todos(ll n, ll curid, vl &cur){
	if(curid == n){
		ll sz = st.size();
		st.insert(cur);
		if(st.size() == sz){
			return;
		}
		/*cout << x+1 << ed;
		ff(i, 0, n){
			cout << cur[i] << " ";
			if((i+1)%3 == 0){
				cout << ed;
			}
		}
		cout << ed << ed;*/
		vl var = cur;
		vl ref(9);
		
		ref[0] = var[2];
		ref[1] = var[1];
		ref[2] = var[0];
		ref[3] = var[5];
		ref[4] = var[4];
		ref[5] = var[3];
		ref[6] = var[8];
		ref[7] = var[7];
		ref[8] = var[6];
		
		st.insert(var);
		st.insert(ref);
		mp[var] = pre[x];
		mp[ref] = pre[x];
		
		var[0] = cur[6];
		var[1] = cur[3];
		var[2] = cur[0];
		var[3] = cur[7];
		var[4] = cur[4];
		var[5] = cur[1];
		var[6] = cur[8];
		var[7] = cur[5];
		var[8] = cur[2];
		
		ref[0] = var[2];
		ref[1] = var[1];
		ref[2] = var[0];
		ref[3] = var[5];
		ref[4] = var[4];
		ref[5] = var[3];
		ref[6] = var[8];
		ref[7] = var[7];
		ref[8] = var[6];
		
		st.insert(var);
		st.insert(ref);
		mp[var] = pre[x];
		mp[ref] = pre[x];
		
		var[0] = cur[8];
		var[1] = cur[7];
		var[2] = cur[6];
		var[3] = cur[5];
		var[4] = cur[4];
		var[5] = cur[3];
		var[6] = cur[2];
		var[7] = cur[1];
		var[8] = cur[0];
		
		ref[0] = var[2];
		ref[1] = var[1];
		ref[2] = var[0];
		ref[3] = var[5];
		ref[4] = var[4];
		ref[5] = var[3];
		ref[6] = var[8];
		ref[7] = var[7];
		ref[8] = var[6];
		
		st.insert(var);
		st.insert(ref);
		mp[var] = pre[x];
		mp[ref] = pre[x];
		
		var[0] = cur[2];
		var[1] = cur[5];
		var[2] = cur[8];
		var[3] = cur[1];
		var[4] = cur[4];
		var[5] = cur[7];
		var[6] = cur[0];
		var[7] = cur[3];
		var[8] = cur[6];
		
		ref[0] = var[2];
		ref[1] = var[1];
		ref[2] = var[0];
		ref[3] = var[5];
		ref[4] = var[4];
		ref[5] = var[3];
		ref[6] = var[8];
		ref[7] = var[7];
		ref[8] = var[6];
		
		st.insert(var);
		st.insert(ref);
		mp[var] = pre[x];
		mp[ref] = pre[x];
		
		x++;
		return;
	}
	vl a = cur;
	todos(n, curid+1, a);
	a[curid] = 1;
	todos(n, curid+1, a);
}

int biggest_stadium(int n, std::vector<std::vector<int>> F){
	ll dd = 0;
	ll xx, y;
	ff(i, 0, n){
		ff(j, 0, n){
			if(F[i][j] == 1){
				xx = j;
				y = i;
				dd++;
			}
		}
	}
	if(dd == 1){
		ll minn = (xx+1)*(y+1);
		//cout << (xx+1)*(y+1) << ed;
		minn = min(minn, (xx+1)*(n-y));
		//cout << (xx+1)*(n-y) << ed;
		minn = min(minn, (n-xx)*(y+1));
		//cout << (n-xx)*(y+1) << ed;
		minn = min(minn, (n-xx)*(n-y));
		//cout << (n-xx)*(n-y) << ed;
		return (n*n)-minn;
	}
	if(n == 1){
		if(F[0][0] == 1){
			return 0;
		}
		else{
			return 1;
		}
	}
	if(n == 2){
		vl flat;
		ff(i, 0, n){
			ff(j, 0, n){
				flat.pb(F[i][j]);
			}
		}
		vl a = {0, 0, 0, 0};
		if(flat == a){
			return 4;
		}
		a = {1, 1, 1, 1};
		if(flat == a){
			return 0;
		}
		a = {0, 0, 0, 1};
		vl b = {0, 0, 1, 0}, c = {0, 1, 0, 0}, d = {1, 0, 0, 0};
		if(flat == a || flat == b || flat == c || flat == d){
			return 3;
		}
		a = {0, 0, 1, 1};
		b = {0, 1, 0, 1};
		c = {1, 0, 1, 0};
		d = {1, 1, 0, 0};
		if(flat == a || flat == b || flat == c || flat == d){
			return 2;
		}
		return 1;
	}
	if(n == 3){
		vl trash(9, 0);
		todos(9, 0, trash);
		vl now;
		ff(i, 0, n){
			ff(j, 0, n){
				now.pb(F[i][j]);
			}
		}
		return mp[now];
	}
    return n*n;
}
/*
void x(){
	cout << "{";
	ff(i, 0, 102){
		ll a;
		cin >> a;
		cout << a << ", ";
	}
	cout << "}";
}*/
/*
int main()
{
	vl t(9, 0);
    todos(9, 0, t);
    //x();
}*/
/*
int main()
{
    int N;
    assert(1 == scanf("%d", &N));
    std::vector<std::vector<int>> F(N, std::vector<int>(N));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            assert(1 == scanf("%d", &F[i][j]));
        }
    }
    fclose(stdin);

    int res = biggest_stadium(N, F);

    printf("%d\n", res);
    fclose(stdout);
    return 0;
}
//Por el vjudge
*/

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30