| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1124551 | crescentp | Tracks in the Snow (BOI13_tracks) | C++20 | 0 ms | 0 KiB |
#ifdef ONLINE_JUDGE
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#endif
#ifndef ONLINE_JUDGE
#include "../pch.h"
#include "diff.cpp"
#endif
#pragma GCC optimize("O3")
using namespace __gnu_pbds;
using namespace std;
/*greater_equal means decreasing ordered_multiset.
use less_than for normal ordered_set*/
template<class T> using ordered_set = tree<T, null_type, greater_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// Operator overloads
template<typename T1, typename T2> // cin >> pair<T1, T2>
istream& operator>>(istream& istream, pair<T1, T2>& p) { return (istream >> p.first >> p.second); }
template<typename T> // cin >> vector<T>
istream& operator>>(istream& istream, vector<T>& v) { for (auto& it : v)cin >> it; return istream; }
template<typename T1, typename T2> // cout << pair<T1, T2>
ostream& operator<<(ostream& ostream, const pair<T1, T2>& p) { return (ostream << p.first << " " << p.second); }
template<typename T> // cout << vector<T>
ostream& operator<<(ostream& ostream, const vector<T>& c) { for (auto& it : c) cout << it << " "; return ostream; }
#define getunique(v) do { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); } while(0)
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define pyes cout << "YES" << endl;
#define pno cout << "NO" << endl;
#define in(n, v) ll n; cin>>n;vector<ll> v(n); rep(i, 0, n) cin>>v[i];
#define in1(n, k, v) ll n, k; cin>>n>>k;vector<ll> v(n); rep(i, 0, n) cin>>v[i];
//#define output(arr) rep(i, 0, arr.size()) cout<<arr[i]<<" ";cout<<endl
#define sumall(arr) long long sum = 0; rep(i, 0, arr.size()) sum+=arr[i]
#define f first
#define s second
#define all(s) s.begin(), s.end()
#define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using ll = long long;
const ll inf = 1e18;
const ll MOD = 1000000000 + 7;
const ll MOD1 = 998244353;
#define pbob cout<<"Bob"<<endl;
#define pali cout<<"Alice"<<endl;
#define pdraw cout<<"Draw"<<endl;
#define int long long
void precomp(){
}
void floodfill(int i, int j, char c,vector<vector<char>> &v, vector<vector<ll>> &vis, set<pair<ll,ll>>&curr){
if(i < 0 || j < 0 || i >= vis.size() || j >= vis[0].size() || vis[i][j] || v[i][j] != c)
return;
vis[i][j] = 1;
curr.insert({i, j});
v[i][j] = (c == 'F') ? 'R' : 'F';
floodfill(i + 1, j , c, v, vis, curr);
floodfill(i , j + 1, c, v, vis, curr);
floodfill(i - 1, j , c, v, vis, curr);
floodfill(i , j - 1, c, v, vis, curr);
}
vector<ll> edges[100005];
void solve() {
ll n, m;cin>>n>>m;
vector<vector<char>> v(n, vector<char>(m));
set<pair<int,int>> marked;
for(int i = 0; i < n; i++){
string b;cin>>b;
for(int j = 0;j < b.length(); j++){
v[i][j] = b[j];
if(v[i][j] != '.'){
marked.insert({i, j});
}
}
}
int animals = 0;
while(1){
set<pair<ll,ll>> curr;
vector<vector<ll>> vis(n, vector<ll>(m, 0));
floodfill(0, 0, v[0][0], v, vis, curr);
animals++;
if(curr == marked)
break;
}
cout<<animals<<endl;
}
/*
READ QUESTION CAREFULLY!!!!!!!!!!
"A" questions are mostly bruteforce. check constraints.
Finding out things that wouldn't matter anyway is important
- Like adding a lot of numbers with some numbers floor, the main part of the integer except-
the remainder would be added anyway. So do it initially itself.
For observation problems
- Think of related problems. Give loose consoints/windowtraints and think of larger p size etc. Solve to gain insight..
- Think of opposite case of what is asked. max asked -> find min and look for pattern.
For Ad-hoc problems try to simplify it into some animation (like B's eating A's or point getting closer to some location)
For pattern detection write brute force and check for pattern.
Don't cout<<double it will do scientific notation
In game type questions where people take turns
- It is enough to consider the starting condition of both players.
- Then the roles reverse and hence becomes a recursive DP problem.
- Popular strategy -> copy opponents move
- Sometimes you can change the starting condition and use the same strategy for both players (first player gets an extra move,
because he's moving first).
PrefixSum
Greedy
Brute Force
Reverse Order
a/b mod m = a* (b^(mod-2)) mod m
a^b mod m = a^(b mod m - 1 ) mod m
a^b^c mod m == a^((b ^ c)mod m - 1)mod m
while taking diff of mods do (diff2 - diff1 + mod) % MOD
String
-pattern should be divisor of whole string
-prefix and suffix
DP
- Bitmask
for(int mask = 1; mask < 1<<n ; mask++)
for(int bit = 0; bit < n; bit++)
Ensure you find all small before big.
**This should be obvious, if you remove any number from (say 234124)- It will be lower
* than the initial one.
Graph
Two Pointers
Binary Search
- If you feel like finding a certain value has too many constraints. It's probably binary searchable.
- Identify by checking for TTTTTFFFFF like cases.
Query
- nlog(n) precompute + log(n) query
Think from reverse
- lose of information from start preventable. Like multiplying and dividing.
Random Function
- Think of special properties it has,
- like merging splitting
INCLUSION EXCLUSION for math
*/
int32_t main() {
fast;
#ifndef ONLINE_JUDGE
clock_t begin = clock();
ifstream input("input.txt");
ofstream outfile("output.txt");
if (!input.is_open()) {
cout << "Failed to open input file." << endl;
return 1;
}
streambuf* cinbuf = cin.rdbuf();
cin.rdbuf(input.rdbuf());
streambuf* coutbuf = cout.rdbuf();
cout.rdbuf(outfile.rdbuf());
#endif
precomp();
ll t = 1;
// cin >> t;
while (t--) {
solve();
}
#ifndef ONLINE_JUDGE
cin.rdbuf(cinbuf);
input.close();
cout.rdbuf(coutbuf);
outfile.close();
clock_t end = clock();
cout << "\n\n\nExecuted In:" << double(end - begin) / CLOCKS_PER_SEC * 1000 << " ms\n";
// compareFiles("output.txt", "expected.txt");
#endif
return 0;
}