Submission #746132

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
746132	2023-05-21T13:22:50 Z	idas	Fire drill (LMIO18_sauga)	C++17	6.1596 / 100	1000 ms	11716 KB

sauga

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define sz(x) ((int)((x).size()))
#define le(vec) vec[vec.size()-1]
#define all(x) (x).begin(), (x).end()
#define TSTS int ttt; cin >> ttt; while(ttt--) solve()
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;

const int INF=1e9, MOD=1e9+7, mod=998244353;
const ll LINF=1e18;

void setIO()
{
    FAST_IO;
}

void setIO(string s)
{
    FAST_IO;
    freopen((s+".in").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

const int N=1e3+10;
int t, n, s, vis[N], adj[N];
bool v[N];
vi ad[N], re[N];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int ops, C;
void go(int u)
{
    int nxt=u;
    while(adj[nxt]!=0){
        if(ops>=C) break;
        ++ops;

        u=nxt;
        vis[u]++;
        int in=rng()%adj[u];

        FOR(i, 0, in)
        {
            if(v[ad[u][i]]) ++in;
        }

        nxt=ad[u][in];
    }
}

void err_vec(vi &vec, int er)
{
    vi nw;
    FOR(i, 0, sz(vec))
    {
        if(vec[i]==er) continue;
        nw.pb(vec[i]);
    }
    vec=nw;
}

void err(int u)
{
    v[u]=true;
    for(auto it : re[u]) adj[it]--;
}

int main()
{
    setIO();
    cin >> t >> n >> s;
    FOR(i, 0, n)
    {
        int x; cin >> x;
        FOR(j, 0, x)
        {
            int b; cin >> b; --b;
            ad[i].pb(b);
            re[b].pb(i);
            adj[i]++;
        }
    }

    vi nodes; FOR(i, 0, n) nodes.pb(i);

    C=int(1e7)/n;
    while(!nodes.empty()){
        FOR(i, 0, n) vis[i]=0;
        ops=0;

        vi nw;
        FOR(i, 0, sz(nodes))
        {
            if(adj[nodes[i]]>0) nw.pb(nodes[i]);
            else{
                int er=nodes[i];

                err(er);

                cout << er+1 << '\n';
            }
        }
        nodes=nw;

        if(nodes.empty()) break;

        while(ops<C){
            int rnd=nodes[rng()%sz(nodes)];
            go(rnd);
        }

//        cout << "sus" << endl;

        int mx=-1;
        FOR(i, 0, n) mx=max(mx, vis[i]);

        FOR(i, 0, n)
        {
            if(vis[i]==mx){
                err_vec(nodes, i);

                err(i);

                cout << i+1 << '\n';
            }
        }

        nw.clear();
        FOR(i, 0, sz(nodes))
        {
            if(adj[nodes[i]]>0) nw.pb(nodes[i]);
            else{
                int er=nodes[i];

                err(er);

                cout << er+1 << '\n';
            }
        }
        nodes=nw;
    }
}

Compilation message

sauga.cpp: In function 'void setIO(std::string)':
sauga.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

6.15960099751 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	255 ms	5700 KB	Output is partially correct
2	Runtime error	9 ms	724 KB	Execution killed with signal 11
3	Runtime error	9 ms	696 KB	Execution killed with signal 11
4	Runtime error	5 ms	724 KB	Execution killed with signal 11
5	Runtime error	6 ms	724 KB	Execution killed with signal 11
6	Runtime error	25 ms	852 KB	Execution killed with signal 11
7	Incorrect	20 ms	1320 KB	Output is not a permutation
8	Execution timed out	1039 ms	11716 KB	Time limit exceeded
9	Runtime error	8 ms	1620 KB	Execution killed with signal 11
10	Partially correct	63 ms	340 KB	Output is partially correct