QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#521400#2199. Intriguing SelectionsocpiteTL 0ms0kbC++231.6kb2024-08-16 10:06:082024-08-16 10:06:08

Judging History

你现在查看的是最新测评结果

  • [2024-08-16 10:06:08]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [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

output:


result: