CSES - Datatähti 2018 loppu - Results
Submission details
Task:Merkkijono
Sender:Yytsi
Submission time:2019-01-16 14:24:18 +0200
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED100
Test results
testverdicttime
#1ACCEPTED0.03 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.02 sdetails
#4ACCEPTED0.01 sdetails
#5ACCEPTED0.02 sdetails

Compiler report

input/code.cpp: In function 'int idx_of_char(int)':
input/code.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Code

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define IO ios_base::sync_with_stdio(0); cin.tie(0)
#define ff first
#define ss second
#define pb push_back
#define INF 2147483647
#define LINF (1LL<<61LL)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;

vector<int> v, op;

int idx_of_char(int c) {
  FOR(i,0,26) if (v[i] == c) return i;
}

bool isSorted() {
  FOR(i,0,26-1) if (v[i] > v[i+1]) return false;
  return true;
}

void mv() {
  op.pb(1);
  int last = v[25];
  v.pop_back();
  v.insert(v.begin(), last);
}

void sw() {
  op.pb(2);
  swap(v[0], v[1]);
}

void move_loc(int x) {
  int idx = idx_of_char(x);
  // Retain order of f = [0..x-1]
  int pass = idx - x;
  while (v[0] != x) mv();

  // Add f [0..x-1] range before x => *f x
  FOR(i,0,pass) mv(), sw();
  while (v[x] != x) mv();
}

int main() {
  IO; string s; cin>>s;
  for (char c : s) v.pb((int)c - 65);


  FOR(i,0,26) {
    if (isSorted()) break;
    move_loc(i);
  }

  cout<<op.size()<<"\n";
  for (int k : op) {
    if (k == 1) cout<<"MOVE\n";
    else cout<<"SWAP\n";
  }
}

Test details

Test 1

Verdict: ACCEPTED

input
ABCDEFGHIJKLMNOPQRSTUVWXYZ

correct output
0

user output
0

Test 2

Verdict: ACCEPTED

input
ZYXWVUTSRQPONMLKJIHGFEDCBA

correct output
923
MOVE
MOVE
SWAP
MOVE
...

user output
975
MOVE
MOVE
SWAP
MOVE
...

Test 3

Verdict: ACCEPTED

input
RPJMFWBHYQOTXUAENLDGZISCVK

correct output
611
SWAP
MOVE
MOVE
SWAP
...

user output
795
MOVE
MOVE
MOVE
MOVE
...

Test 4

Verdict: ACCEPTED

input
GWJSPBHANMXYFLKIDORVUCEZQT

correct output
659
MOVE
SWAP
MOVE
SWAP
...

user output
715
MOVE
MOVE
MOVE
MOVE
...

Test 5

Verdict: ACCEPTED

input
BJYNFLKEIUCZMQHRAXOGWPSDTV

correct output
624
MOVE
SWAP
MOVE
SWAP
...

user output
756
MOVE
MOVE
MOVE
MOVE
...