Submission #1238721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238721		santi3223	Aliens (IOI16_aliens)	C++20	0 / 100	0 ms	324 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
#define ll long long
#define vl vector<ll>
#define all(aaa) aaa.begin(), aaa.end()
#define ff(aa, bb, cc) for(ll aa = bb; aa < cc; aa++)
#define vb vector<bool>
#define ed "\n"
#define pb push_back
#define pll pair<ll, ll>

ll minn;
set<pll> points;
set<vector<vb>> todos;
ll K, M;
ll q = 0;

void brute(ll curk, vector<vb> visited, ll qq){
	if(curk == K){
		bool ok = true;
		for(auto &[a, b] : points){
			if(visited[a][b] == 0){
				ok = false;
				return;
			}
		}
		if(!ok){
			return;
		}
		minn = min(minn, qq);
		/*if(x == minn){
			ff(i, 0, M){
				ff(j, 0, M){
					cout << visited[i][j] << " ";
				}
				cout << ed;
			}
			cout << ed;
		}*/
		return;
	}
	ll sz = todos.size();
	todos.insert(visited);
	if(sz == todos.size()){
		return;
	}
	if(qq > minn){
		return;
	}
	q++;
	brute(curk+1, visited, qq);
	ff(i, 0, M){
		ff(j, i, M){
			vector<vb> nuevo = visited;
			//i---j
			//|   |
			//|---x
			ll nw = qq;
			ll dist = j-i+1;
			ff(curi, i, i+dist){
				ff(curj, i, i+dist){
					if(nuevo[curi][curj] == 0){
						nw++;
					}
					nuevo[curi][curj] = 1;
				}
			}
			if(nuevo != visited){
				brute(curk+1, nuevo, nw);
			}
		}
	}
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c){
	bool ok = true;
	K = k;
	M = m;
	unordered_set<ll> dif;
	ff(i, 0, n){
		points.insert({r[i], c[i]});
		dif.insert(r[i]);
		if(r[i] != c[i]){
			ok = false;
		}
	}
	if(ok){
		return dif.size();
	}
	vector<vb> visited(m, vb(m, 0));
	//cout << m*m << ed;
	minn = m*m;
	
	brute(0, visited, 0);
	cout << q << ed;
	return minn;
}
/*
int main() {
    int n, m, k;
    assert(3 == scanf("%d %d %d", &n, &m, &k));
    std::vector<int> r(n), c(n);
    for (int i = 0; i < n; i++) {
        assert(2 == scanf("%d %d", &r[i], &c[i]));
    }
    long long ans = take_photos(n, m, k, r, c);
    
    
    printf("%lld\n", ans);
    return 0;
}
*/

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40