제출 #1241802

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241802		santi3223	Soccer Stadium (IOI23_soccer)	C++20	35.50 / 100	235 ms	31884 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 < (ll)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 tree = 0;
	ll xxx, yyy;
	ff(i, 0, n){
		ff(j, 0, n){
			if(F[i][j] == 1){
				xxx = j;
				yyy = i;
				tree++;
			}
		}
	}
	if(tree == 1){
		ll minn = (xxx+1)*(yyy+1);
		//cout << (xxx+1)*(yyy+1) << ed;
		minn = min(minn, (xxx+1)*(n-yyy));
		//cout << (xxx+1)*(n-yyy) << ed;
		minn = min(minn, (n-xxx)*(yyy+1));
		//cout << (n-xxx)*(yyy+1) << ed;
		minn = min(minn, (n-xxx)*(n-yyy));
		//cout << (n-xxx)*(n-yyy) << 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];
	}
	
	//bool absno = false;
	ff(i, 0, n){
		ll cur = -1, q = 0;
		ff(j, 0, n){
			if(cur == -1 && F[i][j] == 1){
				continue;
			}
			else if(cur == -1 && F[i][j] != 1){
				cur = 0;
				q++;
				continue;
			}
			if(F[i][j] == cur){
				continue;
			}
			else{
				cur = F[i][j];
				q++;
			}
		}
		if(q >= 3){
			//absno = true;
			return 0;
		}
	}
	ff(j, 0, n){
		ll cur = -1, q = 0;
		ff(i, 0, n){
			if(cur == -1 && F[i][j] == 1){
				continue;
			}
			else if(cur == -1 && F[i][j] != 1){
				cur = 0;
				q++;
				continue;
			}
			if(F[i][j] == cur){
				continue;
			}
			else{
				cur = F[i][j];
				q++;
			}
		}
		if(q >= 3){
			return 0;
		}
	}
	ll q0 = (n*n)-tree;
	vector<pll> range;
	ff(i, 0, n){
		ll a = -1, b = -1;
		ff(j, 0, n){
			if(F[i][j] == 0 && (j == 0 || (j > 0 && F[i][j-1] == 1))){
				a = j;
			}
			if(F[i][j] == 0 && (j == n-1 || (j < n-1 && F[i][j+1] == 1))){
				b = j;
			}
		}
		if(a != -1){
			range.pb({a, b});
		}
	}
	ff(i, 0, range.size()){
		ff(j, i+1, range.size()){
			if((range[i].fi < range[j].fi && range[i].se < range[j].se) || (range[i].fi > range[j].fi && range[i].se > range[j].se)){
				return 0;
			}
		}
	}
	
	return q0;
}
/*
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;
}
*/

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