Submission #1559471


Source Code Expand

#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <random>
#include <bitset>
#include <cassert>
#include <tuple>
#include <list>
#include <iterator>
#include <unordered_set>
#include <unordered_map>
#include <numeric>

using namespace std;

typedef long long ll;
typedef long double ld;

template<class htpe, class cmp>
using heap = priority_queue<htpe, vector<htpe>, cmp>;

template<class htpe>
using min_heap = heap<htpe, greater<htpe> >;

template<class htpe>
using max_heap = heap<htpe, less<htpe> >;

#define mp make_pair
#define pb push_back
#define mt make_tuple
#define ff first
#define ss second

#define forn(i, n) for (int i = 0; i < ((int)(n)); ++i)
#define forrn(i, s, n) for (int i = (int)(s); i < ((int)(n)); ++i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

#define PYMOD(a, m) ((((a) % (m)) + (m)) % (m))

const int INF = 1791791791;
const ll INFLL = 1791791791791791791ll;

template<int input_buf_size, int output_buf_size>
class FastIO {
    char cbuf[input_buf_size + 1];
    int icur = 0;

    inline bool go_to_next_token() {
        while (cbuf[icur] == ' ' || cbuf[icur] == '\n') icur++;
        while (cbuf[icur] == 0) {
            icur = 0;
            if (fgets(cbuf, sizeof(cbuf), stdin) != cbuf)
                return false;
            while (cbuf[icur] == ' ' || cbuf[icur] == '\n') icur++;
        }
        return true;
    }
  public:
    string readString() {
        assert(go_to_next_token());
        string ans;
        while (cbuf[icur] != ' ' && cbuf[icur] != '\n' && cbuf[icur] != 0)
            ans.push_back(cbuf[icur++]);
        ans.shrink_to_fit();
        return ans;
    }

    template<class int_type>
    int_type readInt() {
        assert(go_to_next_token());
        int_type x = 0;
        bool m = cbuf[icur] == '-';
        if (m) icur++;
        while ('0' <= cbuf[icur] && cbuf[icur] <= '9') {
            x *= 10;
            x += (cbuf[icur] - '0');
            icur++;
        }
        if (m) x = -x;
        return x;
    }

    bool seekEof() {
        return !go_to_next_token();
    }

  private:
    char obuf[output_buf_size + 1];
    int ocur = 0;

    inline void write_string(const char *str, size_t sz = 0) {
        if (sz == 0)
            sz = strlen(str);
        if (ocur + sz > output_buf_size) {
            fputs(obuf, stdout);
            fputs(str, stdout);
            ocur = 0;
            obuf[0] = 0;
            return;
        }
        strcpy(obuf + ocur, str);
        ocur += sz;
        obuf[ocur] = 0;
   }

  public:
    template<class int_type>
    void writeInt(int_type x, bool sp = true) {
        char buf[21];
        int c = 0;
        if (x < 0) {
            buf[c++] = '-';
            x = -x;
        }
        int s = c;
        if (x == 0) {
            buf[c++] = '0';
        }
        while (x > 0) {
            buf[c++] = (x % 10) + '0';
            x /= 10;
        }
        for (int i = 0; 2 * i < c - s; i++) {
            swap(buf[s + i], buf[c - 1 - i]);
        }
        buf[c] = 0;
        write_string(buf, c);
        if (sp)
            write_string(" ", 1);
    }

    void writeString(string s, bool space = true) {
        write_string(s.c_str(), s.size());
        if (space)
            write_string(" ", 1);
    }

    void writeEndl() {
        write_string("\n", 1);
#ifdef LOCAL
        if (lflush)
            flush();
#endif
 
    }

    void flush() {
        fputs(obuf, stdout);
        ocur = 0;
        obuf[0] = 0;
    }

private:
    bool lflush;

public:

    FastIO(bool local_flush) { 
        obuf[0] = 0;
        lflush = local_flush;
    }
    
    ~FastIO() {
        fputs(obuf, stdout);
    }
};

FastIO<10000000, 10000000> IO(true);

int main() {
    // Code here:
   
    int n = IO.readInt<int>();
    vector<int> p(n);
    forn(i, n)
        p[i] = IO.readInt<int>() - 1;

    int ans = 0;
    forn(i, n) {
        if (p[i] == i) {
            int j = i + 1;
            if (j == n)
                j -= 2;
            swap(p[i], p[i + 1]);
            ans++;
        }
    }

    forn(i, n)
        assert(p[i] != i);

    IO.writeInt(ans);
    IO.writeEndl();

    return 0;
}

Submission Info

Submission Time
Task D - Derangement
User platypus179
Language C++14 (GCC 5.4.1)
Score 400
Code Size 4627 Byte
Status AC
Exec Time 3 ms
Memory 3200 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 4
AC × 15
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt
Case Name Status Exec Time Memory
0_000.txt AC 1 ms 2304 KB
0_001.txt AC 1 ms 2304 KB
0_002.txt AC 1 ms 2304 KB
0_003.txt AC 1 ms 2304 KB
1_004.txt AC 1 ms 2304 KB
1_005.txt AC 3 ms 3200 KB
1_006.txt AC 3 ms 3200 KB
1_007.txt AC 3 ms 3200 KB
1_008.txt AC 3 ms 3200 KB
1_009.txt AC 3 ms 3200 KB
1_010.txt AC 3 ms 3200 KB
1_011.txt AC 3 ms 3200 KB
1_012.txt AC 3 ms 3200 KB
1_013.txt AC 3 ms 3200 KB
1_014.txt AC 3 ms 3200 KB