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 |
|
|
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 |