QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#521400 | #2199. Intriguing Selection | socpite | TL | 0ms | 0kb | C++23 | 1.6kb | 2024-08-16 10:06:08 | 2024-08-16 10:06:08 |
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn = 205;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> g[maxn], rg[maxn];
bool vis[maxn];
void dfs(int x, int &cnt){
vis[x] = 1;
cnt++;
for(auto v: g[x])if(!vis[v])dfs(v, cnt);
}
void rdfs(int x, int &cnt){
vis[x] = 1;
cnt++;
for(auto v: rg[x])if(!vis[v])rdfs(v, cnt);
}
int main() {
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<pair<int, int>> vec;
for(int i = 1; i <= 2*n; i++){
for(int j = 1; j < i; j++)vec.push_back({i, j});
}
shuffle(vec.begin(), vec.end(), rng);
for(auto p: vec){
bool f1 = 0, f2 = 0;
int cnt = 0;
memset(vis, 0, sizeof(vis));
dfs(p.first, cnt);
if(cnt > n)f1 = 1;
memset(vis, 0, sizeof(vis));
rdfs(p.first, cnt);
if(cnt > n)f1 = 1;
cnt = 0;
memset(vis, 0, sizeof(vis));
dfs(p.second, cnt);
if(cnt > n)f2 = 1;
cnt = 0;
memset(vis, 0, sizeof(vis));
rdfs(p.second, cnt);
if(cnt > n)f2 = 1;
if(f1 && f2)continue;
char c;
cin >> c;
if(c == '>'){
g[p.first].push_back(p.second);
rg[p.second].push_back(p.first);
}
else {
rg[p.first].push_back(p.second);
g[p.second].push_back(p.first);
}
}
cout << "!" << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
2 3